什么是鏈表
鏈表(Linked List)是一種常見的線性結(jié)構(gòu)。它不需要一塊連續(xù)的內(nèi)存空間，通過指針即可將一組零散的內(nèi)存塊串聯(lián)起來。
我們把內(nèi)存塊存為鏈表的節(jié)點(diǎn)，為了將所有的節(jié)點(diǎn)串起來，每個(gè)鏈表的節(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)之外，還需要記錄鏈表的下一個(gè)節(jié)點(diǎn)的地址，這個(gè)記錄下個(gè)節(jié)點(diǎn)地址的指針我們叫做后驅(qū)指針。
搜索鏈表需要O(N)的時(shí)間復(fù)雜度，這點(diǎn)和數(shù)組類似，但是鏈表不能像數(shù)組一樣，通過索引的方式以O(shè)(1)的時(shí)間讀取第n個(gè)數(shù)。
鏈表的優(yōu)勢(shì)在于能夠以較高的效率在任意位置插入或者刪除一個(gè)節(jié)點(diǎn)。
鏈表有哪些類別
單向鏈表
每個(gè)節(jié)點(diǎn)有一個(gè)next指針指向后一個(gè)節(jié)點(diǎn)，還有一個(gè)成員變量用于存儲(chǔ)數(shù)值。
單向鏈表中有兩個(gè)節(jié)點(diǎn)比較特殊，分別是頭結(jié)點(diǎn)和尾節(jié)點(diǎn)。
頭結(jié)點(diǎn)用來記錄鏈表的基地址，知道頭結(jié)點(diǎn)我們就可以遍歷得到整條鏈表。尾結(jié)點(diǎn)的特殊在于指針指向的是一個(gè)空指針NULL。
循環(huán)鏈表
循環(huán)鏈表是一種特殊的單鏈表，與單鏈表不同的是尾節(jié)點(diǎn)不指向空地址，指向鏈表的頭結(jié)點(diǎn)。
優(yōu)點(diǎn)是從鏈尾到鏈頭比較方便，當(dāng)要處理的數(shù)據(jù)具有環(huán)形結(jié)構(gòu)特點(diǎn)是，非常適合用循環(huán)鏈表來處理。
雙向鏈表
雙向鏈表支持兩個(gè)方向，每個(gè)節(jié)點(diǎn)不只有一個(gè)后驅(qū)指針next指向后面的節(jié)點(diǎn)，還有一個(gè)前驅(qū)指針prev指向前面的節(jié)點(diǎn)。
雙向循環(huán)鏈表
鏈表與數(shù)組的性能對(duì)比
時(shí)間復(fù)雜度數(shù)組鏈表
插入刪除O(n)O(1)
隨機(jī)訪問O(1)O(n)
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：動(dòng)態(tài)擴(kuò)容，不需要占用過多的內(nèi)存
缺點(diǎn)：不能隨機(jī)訪問，如果要訪問一個(gè)元素的話，不能根據(jù)索引訪問，只能從頭開始遍歷，找到對(duì)應(yīng)的元素
常用技巧
使用dummy node
dummy node就是在鏈表的head前加一個(gè)節(jié)點(diǎn)指向head，即dummy->head，可以理解成一個(gè)虛擬節(jié)點(diǎn)。多針對(duì)于單鏈表沒有前向指針的問題，保證鏈表的head不會(huì)在刪除操作中丟失。通常情況下，如果鏈表的head會(huì)發(fā)生變化，譬如刪除或者被修改等，可以創(chuàng)建dummy node：
ListNode dummy = new ListNode(0);
dummy.next = head;
這樣就使得操作head節(jié)點(diǎn)與操作其他節(jié)點(diǎn)沒有區(qū)別。
雙指針法
對(duì)于尋找鏈表的某個(gè)特定位置，或者判斷是否有環(huán)等問題時(shí)，可以用兩個(gè)指針變量fast和slow:
ListNode slow = head;
ListNode fast = head;
以不同的速度遍歷該鏈表，以找到目標(biāo)位置。
注意：在測(cè)試時(shí)，需要分別選取鏈表長(zhǎng)度為奇數(shù)和偶數(shù)的test case，可以驗(yàn)證算法在一般情況下的正確性避免遺漏。
交換節(jié)點(diǎn)的處理
如果需要交換兩個(gè)節(jié)點(diǎn)的位置，譬如LeetCode24題：Swap Nodes in Pairs,需要交換兩個(gè)相鄰位置的節(jié)點(diǎn)，對(duì)于這兩個(gè)前驅(qū)節(jié)點(diǎn)，他們的next指針會(huì)受到影響，這兩個(gè)節(jié)點(diǎn)本身也會(huì)受到影響，可以用以下步驟：
1）先交換兩個(gè)前驅(qū)節(jié)點(diǎn)的next指針的值
2）再交換這兩個(gè)節(jié)點(diǎn)的next指針的值
無論這兩個(gè)節(jié)點(diǎn)的相對(duì)位置和絕對(duì)位置如何，以上的處理方式均可成立
同時(shí)操作兩個(gè)鏈表的處理
遇到這種題目，循環(huán)的條件一般可以用while（list1 && list2），當(dāng)循環(huán)跳出來后，再處理剩下非空的鏈表，這相當(dāng)于：邊界情況特殊處理，常規(guī)情況常規(guī)處理。
題型總結(jié)
基本操作
刪除類
例題：19 Remove Nth Node From End of List 【Medium】
題意：刪除鏈表中倒數(shù)第n個(gè)節(jié)點(diǎn)
test case:
Given linked list: 1->2->3->4->5, and n = 2.
刪除鏈表中導(dǎo)數(shù)第二個(gè)節(jié)點(diǎn)，變成1->2->3->5.
解題思路：雙指針法
在head前加一個(gè)虛擬節(jié)點(diǎn)dummy node，并設(shè)置兩個(gè)指針fast和slow。
fast指針現(xiàn)象前移動(dòng)n個(gè)節(jié)點(diǎn)（從dummy節(jié)點(diǎn)開始移動(dòng)，所以實(shí)際上是移動(dòng)到了n-1位），然后fast和slow同時(shí)開始移動(dòng)，當(dāng)fast.next == None時(shí)，slow節(jié)點(diǎn)指向的就是需要?jiǎng)h除的節(jié)點(diǎn)前面的一個(gè)節(jié)點(diǎn)，將其指向.next.next即可
code：
Java
class Solution{
public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy;
ListNode slow = dummy;
while(fast.next != null){
if(n <>0)
slow = slow.next;
fast = fast.next;
n--;
}
if(slow.next != null)
slow.next = slow.next.next;
return dummy.next;
}
}
Python
class Solution:
def removeNthFromEnd(self, head, n):
fast = slow = head
for _ in range(n):
fast = fast.next
if not fast:
return head.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
復(fù)雜度分析：時(shí)間復(fù)雜度O(length(list)), 即O(N)，空間復(fù)雜度O(1)
Leetcode中包含刪除類的題目：
序號(hào)題目難度代碼
19Remove Nth Node From End of List mediumpython、java、c++
82Remove Duplicates from Sorted List II Mediumpython、java、c++
83Remove Duplicates from Sorted List Easypython、java、c++
203Remove Linked List Elements Easypython、java、c++
237Delete Node in a Linked List Easypython、java、c++
翻轉(zhuǎn)類題型
最基礎(chǔ)最常在面試中遇到的題型，206、92一定要熟練掌握
例題1：206 Reverse Linked List 【easy】
題意：翻轉(zhuǎn)一個(gè)單向鏈表
test case:
Input：1->2->3->4->5->NULL
Output：5->4->3->2->1->NULL
思考：可否用迭代和遞歸兩種方法完成？
解題思路：對(duì)于翻轉(zhuǎn)類的題型，我們只需要知道head->prev節(jié)點(diǎn)如何翻轉(zhuǎn)成prev-head即可。
這里我們?nèi)匀灰玫絛ummy node，作為head的前驅(qū)節(jié)點(diǎn)，在翻轉(zhuǎn)前，是dummy->head->2->3…->NULL。
而翻轉(zhuǎn)后變成NULL->5->…->2->head->dummy，dummy變成了尾節(jié)點(diǎn)。
因?yàn)檫@是一個(gè)單向鏈表，head只有一個(gè)指針，已經(jīng)指向了下一個(gè)節(jié)點(diǎn)了，所以首先需要把head的下一個(gè)節(jié)點(diǎn)，即head.next用一個(gè)臨時(shí)變量存儲(chǔ)起來，與head'斷開連接'。
這樣，head就可以指向dummy了，即我們將dummy->head變成了head->dummy，第一步完成。
后面的處理方式有兩種寫法，一種是迭代，我們可以再來用同樣的方式處理head->head.next ,使之變成head.next->head。
同樣讓head.next.next用一個(gè)變量存儲(chǔ)起來，斷開與head.next的連接，然后head.next指向head即可，在這里其實(shí)head.next.next就相當(dāng)于第一步中的head.next，head.next就相當(dāng)于第一步的dummy,所以可以直接寫成dummy = head，head = next；
遞歸的方式則需要c創(chuàng)建一個(gè)遞歸函數(shù)，把第一步的步驟寫入遞歸函數(shù)里面，然后再不斷地調(diào)用這個(gè)遞歸函數(shù)即可。
code：
Java
/*迭代寫法*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null){
return head;
}
ListNode dummy = null;
while (head != null){
ListNode next = head.next;
head.next = dummy;
dummy = head;
head = next;
}
return dummy;
}
}
/*遞歸寫法*/
class Solution{
public ListNode reverseList(ListNode head) {
return reverseListHelper(head, null);
}
private ListNode reverseListHelper(ListNode head, ListNode newHead) {
if (head == null)
return newHead;
ListNode next = head.next;
head.next = newHead;
return reverseListHelper(next, head);
}
}
Python
# 迭代寫法
class Solution(object):
def reverseList(self, head):
'''
:type head: ListNode
:rtype: ListNode
'''
dummy = None
while head :
next = head.next
head.next = dummy
dummy = head
head = next
return dummy
# 遞歸寫法
class Solution(object):
def reverseList(self,head):
'''
:type head: ListNode
:rtype: ListNode
'''
return self.reverseListHelper(head)
def reverseListHelper(self,head,dummy=None):
if not head:
return dummy
next = head.next
head.next = dummy
return self.reverseListHelper(next,head)
復(fù)雜度分析：
復(fù)雜度迭代法遞歸法
時(shí)間復(fù)雜度O(N)O(N)
空間復(fù)雜度O(1)O(N)
例題2：92 Reverse Linked List 【medium】
題意：從m->n的位置翻轉(zhuǎn)鏈表()
test case:
Input:1->2->3->4->5->NULL, m = 2, n = 4
Output:1->4->3->2->5->NULL
解題思路：迭代法。
翻轉(zhuǎn)鏈表第一步找起始位置和它前面的節(jié)點(diǎn)，頭結(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)我們還是設(shè)置dummy，從m->n翻轉(zhuǎn)，那么在開始處設(shè)置為start node，后驅(qū)節(jié)點(diǎn)設(shè)置為then, 即start.next = then，來幫助我們翻轉(zhuǎn)。
以test case 為例，下面是第一次翻轉(zhuǎn)：
第一次翻轉(zhuǎn)完成之后，如圖所示：
由 dummy->1 - 2 - 3 - 4 - 5 變成了 dummy->1 - 3 - 2 - 4 - 5。
同理，迭代，第二次翻轉(zhuǎn)后 由 dummy->1 - 3 - 2 - 4 - 5 變成 dummy->1 - 4 - 3 - 2 - 5，翻轉(zhuǎn)結(jié)束。
簡(jiǎn)單來說，相當(dāng)于不斷地交換then和start，然后將then后移直到結(jié)束。
code：
Java
/*迭代法*/
class Solution{
public ListNode reverseBetween(ListNode head, int m, int n) {
if(head == null) return null;
ListNode dummy = new ListNode(0); // 創(chuàng)建一個(gè) dummy node 標(biāo)記這個(gè)鏈表的head
dummy.next = head;
ListNode pre = dummy;
// dummy-> 1 -> 2 -> 3 -> 4 -> 5
for(int i = 0; i<>1; i++) pre = pre.next;
ListNode start =pre.next;
ListNode then = start.next; // 創(chuàng)建一個(gè) then node 幫助后面翻轉(zhuǎn)
// 1 - 2 -3 - 4 - 5 ; m=2; n =4 ---> pre = 1, start = 2, then = 3
for(int i=0; i<>< span=''>
{
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}
return dummy.next;
}
/*遞歸法*/
class Solution {
private boolean stop;
private ListNode left;
public void recurseAndReverse(ListNode right, int m, int n) {
if (n == 1) {
return;
}
right = right.next; }
public ListNode reverseBetween(ListNode head, int m, int n) {
this.left = head;
this.stop = false;
this.recurseAndReverse(head, m, n);
return head;
}
}
Python
# 迭代法
class Solution(object):
def reverseBetween(self, head, m, n):
dummy = ListNode(0)
dummy.next = head
cur, prev = head, dummy
for _ in xrange(m - 1):
cur = cur.next
prev = prev.next
for _ in xrange(n - m):
temp = cur.next
cur.next = temp.next
temp.next = prev.next
prev.next = temp
return dummy.next
# 遞歸法
class Solution:
def reverseBetween(self, head, m, n):
def reverse(prev, current, m):
nxt = current.next
current.next = prev
if m == 0:
return current, nxt
return reverse(current, nxt, m - 1)
lth = None
mth = head
for i in range(1, m):
lth = mth
mth = mth.next
nth, oth = reverse(lth, mth, n - m)
if lth:
lth.next = nth
else:
head = nth
mth.next = oth
return head
復(fù)雜度分析：
復(fù)雜度迭代法遞歸法
時(shí)間復(fù)雜度O(N)O(N)
空間復(fù)雜度O(1)O(N)
迭代法：時(shí)間復(fù)雜度是O(N), 并且我們是在原鏈表上進(jìn)行指針移動(dòng)的，所以空間復(fù)雜度為O(1)
遞歸法：每個(gè)節(jié)點(diǎn)最多需遍歷兩次，一次是常規(guī)的遞歸，一次是回溯的遞歸，所以時(shí)間復(fù)雜度是O(N)。
在最壞的情況下，我們需要翻轉(zhuǎn)整個(gè)鏈表，并且遞歸的方法會(huì)占用棧，所以空間復(fù)雜度是O(N)
這是兩個(gè)非常典型而且常見的鏈表翻轉(zhuǎn)類題目，在面試中也經(jīng)常出現(xiàn)作為熱身題，所以需要重點(diǎn)關(guān)注。
Leetcode中包含翻轉(zhuǎn)鏈表的題目：
序號(hào)題目難度代碼
25Reverse Nodes in k-Group Hardpython、java、c++
61Rotate List Mediumpython、java、c++
92Reverse Linked List II Mediumpython、java、c++
206Reverse Linked List Easypython、java、c++
合并鏈表
例題：21 Merge Two Sorted Lists 【easy】
題意：將兩個(gè)排序好的鏈表合并成新的有序鏈表
test case:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
解題思路: 迭代法和遞歸法。
迭代法是每次比較兩個(gè)結(jié)點(diǎn)，把較小的加到結(jié)果鏈表中，并且這個(gè)指針向后移動(dòng)；
遞歸法即每次比較兩個(gè)鏈表的頭部，將較小的頭部單獨(dú)取出來，剩下的兩個(gè)部分繼續(xù)遞歸。
code：
Java
/*迭代法*/
class Solution{
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (l1 != null && l2 != null) {
if (l1.val >= l2.val) {
cur.next = l2;
l2 = l2.next;
} else {
cur.next = l1;
l1 = l1.next;
}
cur = cur.next;
}
if (l1 != null)
cur.next = l1;
if (l2 != null)
cur.next = l2;
return head.next;
}
}
/*遞歸法*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val > l2.val) {
ListNode tmp = l2;
tmp.next = mergeTwoLists(l1, l2.next);
return tmp;
} else {
ListNode tmp = l1;
tmp.next = mergeTwoLists(l1.next, l2);
return tmp;
}
}
}
Python
# 迭代法
def mergeTwoLists1(self, l1, l2):
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val <>
cur.next = l1
l1 = l1.next
else:
cur.next = l2
l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next
# 遞歸法
def mergeTwoLists2(self, l1, l2):
if not l1 or not l2:
return l1 or l2
if l1.val <>
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
LeetCode中包含 合并鏈表類的題目：
序號(hào)題目難度代碼
2Add Two Numbers mediumpython、java、c++
21Merge Two Sorted Lists Easypython、java、c++
23Merge k Sorted Lists Hardpython、java、c++
445Add Two Numbers II Mediumpython、java、c++
環(huán)形鏈表
例題：141 Linked List Cycle 【easy】
題意：判斷一個(gè)單鏈表是否存在環(huán)
test case:
Input : head = [3, 2, 0, -4], pos = 1
Output : true
why：在這個(gè)單鏈表中存在一個(gè)環(huán)，尾節(jié)點(diǎn)指向第二個(gè)節(jié)點(diǎn)
解題思路：雙指針法。
這道題可以用雙指針做，有的也叫快慢指針，或者runner and chaser。
什么意思呢？即從頭設(shè)置兩個(gè)指針，一個(gè)快指針走2n步（視具體題目而定），慢指針走n步，當(dāng)快指針走到尾節(jié)點(diǎn)時(shí)，滿指針正好走到鏈表的一半（視具體題目而定）。
在本題中，設(shè)置快指針走兩步，慢指針一次走一步，如果快指針走到了盡頭，則說明鏈表無環(huán)，如果快指針和慢指針相遇就說明鏈表有環(huán)。
為什么呢？我們假設(shè)一個(gè)有環(huán)鏈表，快慢指針最后都會(huì)走到環(huán)上，而這個(gè)環(huán)就像一個(gè)環(huán)形跑道一樣，慢指針在后面，快指針在前面。
但實(shí)際上快指針也在追慢指針，希望能超慢指針一圈。他們?cè)谶@個(gè)跑道上，總會(huì)有一天快指針追上了慢指針。
我們不用擔(dān)心快指針跳過了慢指針，因?yàn)樗麄儍傻乃俣炔钍?，所以它們?cè)诃h(huán)上的距離總是每次減1，最后總能減到0。
code：
Java
class Solution {
public boolean hasCycle(ListNode head) {
if(head==null) return false;
ListNode slow = head;
ListNode fast = head;
while(fast.next!=null && fast.next.next!=null) {
slow = slow.next;
fast = fast.next.next;
if(slow==fast) return true;
}
return false;
}
}
Python
class Solution(object):
def hasCycle(self, head):
'''
:type head: ListNode
:rtype: bool
'''
try:
slow = head
fast = head.next
while slow is not fast:
slow = slow.next
fast = fast.next.next
return True
except:
return False
復(fù)雜度分析：時(shí)間復(fù)雜度O(N)，空間復(fù)雜度 O(1)
LeetCode中含有環(huán)形鏈表的題目：
序號(hào)題目難度代碼
141Linked List Cycle Easypython、java、c++
142Linked List Cycle II Mediumpython、java、c++
708Insert into a Cyclic Sorted List Mediumpython、java、c++
拆分鏈表
例題：86 Partition List 【medium】
題意：給定一個(gè)鏈表以及一個(gè)目標(biāo)值，把小于該目標(biāo)值的所有節(jié)點(diǎn)都移至鏈表的前端，大于或等于目標(biāo)值的節(jié)點(diǎn)移至鏈表的尾端，同時(shí)要保持這兩部分在原先鏈表中的相對(duì)位置。
test case:
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
解題思路: 二分法
設(shè)置兩個(gè)指針left和right，順序遍歷整條鏈表，left、mid、target三者比較，根據(jù)情況left右移或者right左移。關(guān)鍵就在于邊界情況和元素有重復(fù)。
當(dāng) nums[mid] = nums[left] 時(shí)，這時(shí)由于很難判斷 target 會(huì)落在哪，那么只能采取 left++
當(dāng) nums[mid] > nums[left] 時(shí)，這時(shí)可以分為兩種情況，判斷左半部比較簡(jiǎn)單
當(dāng) nums[mid] < nums[left]="">
code：
Java
class Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <>
int mid = (left + right) / 2;
if (target == nums[mid]) return true;
if (nums[mid] == nums[left]) left++;
else if (nums[mid] > nums[left]) {
if (nums[left] <= target=''> target) right = mid - 1;
else left = mid + 1;
} else {
if (nums[mid] <><>1;
else right = mid - 1;
}
}
return false;
}
}
Python
class Solution(object):
def search(self, nums, target):
'''
:type nums: List[int]
:type target: int
:rtype: bool
'''
left, right = 0, len(nums)-1
while left <>
mid = left + (right-left)//2
if nums[mid] == target:
return True
while left <>and nums[left] == nums[mid]:
left += 1
if nums[left] <>
if nums[left] <><>
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] <><>
left = mid + 1
else:
right = mid - 1
return False
LeetCode中含有拆分類的題目:
序號(hào)題目難度代碼
725Split Linked List in Parts Mediumpython、java、c++
86Partition List Mediumpython、java、c++
排序鏈表
例題：148 Sort List【medium】
題意：在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下，對(duì)鏈表進(jìn)行排序
test case:
Input: 4->2->1->3
Output: 1->2->3->4
解題思路 : 歸并排序。
這題有很多解法，題目要有時(shí)間復(fù)雜度是O(nlogn),滿足這個(gè)條件的有快速排序，堆排序，歸并排序，三者的空間復(fù)雜度分別為O(1) 、O(N)、O(N)。
對(duì)于鏈表而言，在進(jìn)行歸并操作時(shí)并不需要像數(shù)組的歸并操作那樣分配一個(gè)臨時(shí)數(shù)組空間，所以是O(1)的空間復(fù)雜度，只需要改變節(jié)點(diǎn)的next指針的指向，就可以表示新的歸并后的順序。
思考：快排和歸并排序的時(shí)間復(fù)雜度都是O(nlogn)，實(shí)踐證明快排的速度比歸并排序的速度更快，對(duì)于數(shù)組排序成立，為什么在鏈表中歸并排序更快呢？（解答見下方）
code：
Java
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
// step 1.把鏈表分成兩半
ListNode prev = null, slow = head, fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
// step 2.對(duì)于每一部分的鏈表進(jìn)行排序
ListNode l1 = sortList(head);
ListNode l2 = sortList(slow);
// step 3. 合并 l2 和 l2
return merge(l1, l2);
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode l = new ListNode(0), p = l;
while (l1 != null && l2 != null) {
if (l1.val <>
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null)
p.next = l1;
if (l2 != null)
p.next = l2;
return l.next;
}
}
Python
class Solution(object):
def sortList(self, head):
if not head or not head.next:
return head
fast, slow = head.next, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
second = slow.next
slow.next = None
l = self.sortList(head)
r = self.sortList(second)
return self.merge(l, r)
def merge(self, l, r):
if not l or not r:
return l or r
if l.val > r.val:
l, r = r, l
head = pre = l
l = l.next
while l and r:
if l.val <>
l = l.next
else:
nxt = pre.next
pre.next = r
tmp = r.next
r.next = nxt
r = tmp
pre = pre.next
pre.next = l or r
return head
思考解答：如果待排序的元素存儲(chǔ)在數(shù)組中，那么快速排序相對(duì)歸并排序就有兩個(gè)原因更快。
其一，可以很快地進(jìn)行元素的讀取(相對(duì)于鏈表，數(shù)組的元素是順序擺放的，而鏈表的元素是隨機(jī)擺放的，數(shù)組的partion這步就比鏈表的partion這步快。
其二，歸并排序在merge階段需要輔助數(shù)組，需要申請(qǐng)O(N)的空間，申請(qǐng)空間也是需要時(shí)間的。
而快排不需要額外申請(qǐng)空間。如果待排序的元素存儲(chǔ)在鏈表中，快排的優(yōu)點(diǎn)就變成了缺點(diǎn)。歸并排序于是就速度更優(yōu)了。
LeetCode中 包含鏈表排序的題目：
序號(hào)題目難度代碼
143Reorder List Mediumpython、java、c++
147Insertion Sort List Mediumpython、java、c++
148Sort List Mediumpython、java、c++
參考資料：
1.http://stackoverflow.com/questions/7629904/why-is-mergesort-better-for-linked-lists
2.https://leetcode.com/problems/sort-list/discuss/46714/Java-merge-sort-solution
3.https://blog.csdn.net/happyaaaaaaaaaaa/article/details/51602234
4.https://leetcode.com/problems/merge-two-sorted-lists/discuss/9735/Python-solutions-(iteratively-recursively-iteratively-in-place).
End
