實(shí)際上，雙指針是一個(gè)很籠統(tǒng)的概念。只要在解題時(shí)用到了兩個(gè)指針（鏈表指針、數(shù)組下標(biāo)皆可），都可以叫做雙指針方法。根據(jù)兩個(gè)指針運(yùn)動(dòng)方式的不同，雙指針方法可以分成同向指針、對(duì)向指針、快慢指針等。
當(dāng)雙指針方法遇到鏈表問題，我們主要使用快慢指針方法。很多時(shí)候鏈表操作遇到疑難雜癥時(shí)，可以使用快慢指針，減少算法所需的時(shí)間或者空間。
鏈表問題中的快慢指針特點(diǎn)
我們知道，鏈表數(shù)據(jù)類型的特點(diǎn)決定了它只能單向順序訪問，而不能逆向遍歷或隨機(jī)訪問（按下標(biāo)訪問）。很多時(shí)候，我們需要使用快慢指針的技巧來實(shí)現(xiàn)一定程序的逆向遍歷，或者減少遍歷的次數(shù)。這就是為什么快慢指針常用于鏈表問題。
例題 1：尋找鏈表中點(diǎn)
LeetCode 876 - Middle of the Linked List[4]（Easy）
尋找鏈表中點(diǎn)的常規(guī)做法是，先遍歷一遍鏈表，計(jì)算鏈表的長(zhǎng)度?。再遍歷一遍鏈表，找到第? n 個(gè)元素。這樣需要遍歷鏈表兩遍。更巧妙的做法是使用一快一慢兩個(gè)指針。
public ListNode middleNode(ListNode head) {
? ? ListNode fast = head;
? ? ListNode slow = head;
? ? while (fast != null && fast.next != null) {
? ? ? ? // fast 一次前進(jìn)兩個(gè)元素，slow 一次前進(jìn)一個(gè)元素
? ? ? ? fast = fast.next.next;
? ? ? ? slow = slow.next;
? ? }
? ? // 鏈表元素為奇數(shù)個(gè)時(shí)，slow 指向鏈表的中點(diǎn)
? ? // 鏈表元素為偶數(shù)個(gè)時(shí)，slow 指向鏈表兩個(gè)中點(diǎn)的右邊一個(gè)
? ? return slow;
}
例題 2：尋找鏈表的倒數(shù)第 k 個(gè)元素
LeetCode 19 - Remove Nth Node From End of List[5]（Medium）
尋找鏈表的倒數(shù)第? 個(gè)元素的常規(guī)做法是，先遍歷一遍鏈表，計(jì)算鏈表的長(zhǎng)度?。這樣就可以計(jì)算出要找第? n個(gè)元素，再遍歷一遍鏈表即可。這里同樣可以使用快慢指針方法減少一次遍歷。
public ListNode removeNthFromEnd(ListNode head, int k) {
? ? // 將 fast 前進(jìn) k 個(gè)元素
? ? ListNode fast = head;
? ? for (int i = 0; i < k; i++) {
? ? ? ? // 這里省略了檢測(cè)空指針的代碼
? ? ? ? fast = fast.next;
? ? }
? ? // fast 和 slow 指針間隔 k 個(gè)同時(shí)前進(jìn)
? ? // 這里使用了鏈表遍歷框架，將 slow 指針變成兩個(gè)指針 curr 和 prev
? ? ListNode curr = head;
? ? ListNode prev = null;
? ? while (fast != null) {
? ? ? ? prev = curr;
? ? ? ? curr = curr.next;
? ? ? ? fast = fast.next;
? ? }
? ? if (prev == null) {
? ? ? ? head = curr.next;
? ? } else {
? ? ? ? prev.next = curr.next;
? ? }
? ? return head;
}
例題 3：判斷鏈表中是否存在環(huán)
LeetCode 141 - Linked List Cycle[6]（Easy）
public boolean hasCycle(ListNode head) {
? ? ListNode fast = head;
? ? ListNode slow = head;
? ? while (fast != null && fast.next != null) {
? ? ? ? fast = fast.next.next;
? ? ? ? slow = slow.next;
? ? ? ? // fast 和 slow 指向同一個(gè)結(jié)點(diǎn)，說明存在“套圈”
? ? ? ? if (fast == slow) {
? ? ? ? ? ? return true;
? ? ? ? }
? ? }
? ? // fast 到達(dá)鏈表尾部，則不存在環(huán)
? ? return false;
}
這一題還有第二問，LeetCode 142 - Linked List Cycle II[7]，找到鏈表入環(huán)的第一個(gè)結(jié)點(diǎn)。
總結(jié)
本文講解的是雙指針技巧中的一類“快慢指針”，用于解決鏈表類問題。而快慢指針又存在著多個(gè)變種，文中也一一列舉了。
鏈表類題目并不復(fù)雜，本系列第一講的鏈表遍歷框架和本文所講的快慢指針就是鏈表類問題中最主要的兩個(gè)技巧了。鏈表類問題只要多加練習(xí)，都非常的容易。
最后，附上一道鏈表問題的綜合練習(xí)題：鏈表排序（LeetCode 148 - Sort List[8]）。這道題中需要使用到鏈表處理的各種技巧，還需要針對(duì)鏈表的性質(zhì)選擇合適的排序方法?？梢哉f只要掌握了這道題，就算掌握了鏈表類問題了。鏈表排序也是微軟面試中某個(gè)面試官的“三板斧”之一，可以看出這道題的普適性。
上一講和這一講我們分別了解了兩種不同類型的雙指針方法：對(duì)向指針和快慢指針。雙指針還有一種經(jīng)典的類型是滑動(dòng)窗口，將在后面的章節(jié)進(jìn)行講解。敬請(qǐng)期待。
歸并排序
歸并排序（Merge sort）是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。
歸并排序的性能不受輸入數(shù)據(jù)的影響，始終都是 O(nlogn) 的時(shí)間復(fù)雜度，代價(jià)是需要額外的內(nèi)存空間。
算法原理
①?把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
②?對(duì)這兩個(gè)子序列分別采用歸并排序；
③?將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。
將兩個(gè)的有序數(shù)列合并成一個(gè)有序數(shù)列，我們稱之為"歸并"。
歸并排序(Merge Sort)就是利用歸并思想對(duì)數(shù)列進(jìn)行排序。根據(jù)具體的實(shí)現(xiàn)，歸并排序包括"從上往下"和"從下往上"2種方式。
1、從下往上的歸并排序：將待排序的數(shù)列分成若干個(gè)長(zhǎng)度為1的子數(shù)列，然后將這些數(shù)列兩兩合并；得到若干個(gè)長(zhǎng)度為2的有序數(shù)列，再將這些數(shù)列兩兩合并；得到若干個(gè)長(zhǎng)度為4的有序數(shù)列，再將它們兩兩合并；直接合并成一個(gè)數(shù)列為止。這樣就得到了我們想要的排序結(jié)果。(參考下面的圖片)
2、從上往下的歸并排序：它與"從下往上"在排序上是反方向的。它基本包括3步：
① 分解：將當(dāng)前區(qū)間一分為二，即求分裂點(diǎn) mid = (low + high)/2;
② 求解：遞歸地對(duì)兩個(gè)子區(qū)間a[low...mid] 和 a[mid+1...high]進(jìn)行歸并排序。遞歸的終結(jié)條件是子區(qū)間長(zhǎng)度為1。
③ 合并：將已排序的兩個(gè)子區(qū)間a[low...mid]和 a[mid+1...high]歸并為一個(gè)有序的區(qū)間a[low...high]。
下面的圖片很清晰的反映了"從下往上"和"從上往下"的歸并排序的區(qū)別。
歸并排序(從上往下)參考小波同學(xué)“歸并排序(從上往下)——內(nèi)存優(yōu)化——推薦方式”代碼；歸并排序(從下往上)參考小波同學(xué)MergeSort2代碼。
鏈表綜合練習(xí)題
LeetCode 148 - Sort List[1]（Medium）: 用 O(nlogn) 級(jí)別的時(shí)間復(fù)雜度、常數(shù)級(jí)空間復(fù)雜度，對(duì)鏈表進(jìn)行排序。
這個(gè)系列到目前為止已經(jīng)講了兩期鏈表類問題了，分別是鏈表遍歷框架、鏈表快慢指針。鏈表類問題并不復(fù)雜，這兩大方法已經(jīng)可以基本涵蓋大部分的鏈表題目了。
本期所講的鏈表排序問題是一道經(jīng)典的鏈表綜合題。在面試中，這道題非常常見，甚至是微軟某面試官常用的”三板斧“之一，足以看出它的普適性。這道題需要用到鏈表問題各種常見的方法和操作。同時(shí)，它又涉及到將傳統(tǒng)的數(shù)組排序方法遷移到鏈表，可以考察面試者對(duì)排序算法的理解。具體來說，鏈表排序這道題可以考察：對(duì)鏈表性質(zhì)的掌握、對(duì)分治法的掌握、對(duì)鏈表操作的掌握
選擇排序方法
首先，我們要理解鏈表問題的基本原則，不使用額外的空間。也就是說，不使用 new 關(guān)鍵字。
明確了這個(gè)原則之后，我們?cè)賮砜催@道題目。題目要求使用? nlogn級(jí)別的排序算法。回顧我們學(xué)過的排序算法，很顯然，我們需要在快速排序、歸并排序、堆排序中進(jìn)行選擇。
鏈表相對(duì)于數(shù)組最大的不同，在于鏈表只能進(jìn)行順序訪問，甚至只能進(jìn)行正向順序訪問，不能進(jìn)行隨機(jī)訪問（按下標(biāo)訪問）。而考慮到快速排序、堆排序都涉及到大量的隨機(jī)訪問，必然排除。剩下的歸并排序，仔細(xì)思考之后，確實(shí)可以只用順序訪問。那么，我們可以將歸并排序方法應(yīng)用到鏈表排序上。
鏈表切分
鏈表的切分需要將鏈表平分為左右兩半。這個(gè)操作實(shí)際上可以拆分為兩個(gè)基本操作：尋找鏈表的中點(diǎn)、刪除鏈表中點(diǎn)左側(cè)的指針，將鏈表斷開。尋找鏈表中點(diǎn)的操作，我們?cè)?b>鏈表快慢指針的文章中講過，使用一快一慢兩個(gè)指針遍歷鏈表即可。刪除鏈表指針，實(shí)際上和刪除鏈表結(jié)點(diǎn)類似。我們?cè)?b>鏈表遍歷框架的文章中講過，使用相鄰的兩個(gè)指針一同遍歷鏈表即可。
那么如何將這兩個(gè)方法融合起來呢？我們使用三個(gè)指針即可，分別是快指針、慢指針、慢指針的前一個(gè)指針。這樣當(dāng)快指針到達(dá)鏈表尾部時(shí)，慢指針的前一個(gè)結(jié)點(diǎn)正好是我們要?jiǎng)h除的指針。
三個(gè)指針的移動(dòng)過程
ListNode split(ListNode head) {
? ? ListNode fast = head;
? ? ListNode slow = head;
? ? ListNode prev = null;
? ? while (fast != null && fast.next != null) {
? ? ? ? fast = fast.next.next;
? ? ? ? prev = slow;
? ? ? ? slow = slow.next;
? ? }
? ? prev.next = null;// 將鏈表斷開
? ? return slow;
}
鏈表合并
如何將兩個(gè)有序的鏈表合并成一整個(gè)有序鏈表呢？其實(shí)，鏈表的合并也是一種基本操作，例如這一題，考的就是鏈表合并：
LeetCode 21 - Merge Two Sorted Lists[3]（Easy）
// 全局變量，用于將結(jié)點(diǎn)插入鏈表尾部
ListNode head;
ListNode tail;
ListNode merge(ListNode left, ListNode right) {
? ? head = null;
? ? tail = null;
? ? ListNode q1 = left;
? ? ListNode q2 = right;
? ? while (q1 != null || q2 != null) {
? ? ? ? if (q1 == null) {
? ? ? ? ? ? append(q2);
? ? ? ? ? ? q2 = q2.next;
? ? ? ? } else if (q2 == null) {
? ? ? ? ? ? append(q1);
? ? ? ? ? ? q1 = q1.next;
? ? ? ? } else if (q1.val < q2.val) {
? ? ? ? ? ? append(q1);
? ? ? ? ? ? q1 = q1.next;
? ? ? ? } else {
? ? ? ? ? ? append(q2);
? ? ? ? ? ? q2 = q2.next;
? ? ? ? }
? ? }
? ? return head;
}
void append(ListNode node) {
? ? if (head == null) {
? ? ? ? head = node;
? ? ? ? tail = node;
? ? } else {
? ? ? ? tail.next = node;
? ? ? ? tail = node;
? ? }
}
全部代碼
到了這里，鏈表排序的全部代碼已經(jīng)完成了。下面是完成的題解代碼：
public ListNode sortList(ListNode head) {
? ? if (head == null || head.next == null) {
? ? ? ? return head;
? ? }
? ? ListNode mid = split(head);
? ? ListNode left = sortList(head);
? ? ListNode right = sortList(mid);
? ? return merge(left, right);
}
ListNode split(ListNode head) {
? ? ListNode fast = head;
? ? ListNode slow = head;
? ? ListNode prev = null;
? ? while (fast != null && fast.next != null) {
? ? ? ? fast = fast.next.next;
? ? ? ? prev = slow;
? ? ? ? slow = slow.next;
? ? }
? ? prev.next = null;
? ? return slow;
}
ListNode head;
ListNode tail;
ListNode merge(ListNode left, ListNode right) {
? ? head = null;
? ? tail = null;
? ? ListNode q1 = left;
? ? ListNode q2 = right;
? ? while (q1 != null || q2 != null) {
? ? ? ? if (q1 == null) {
? ? ? ? ? ? append(q2);
? ? ? ? ? ? q2 = q2.next;
? ? ? ? } else if (q2 == null) {
? ? ? ? ? ? append(q1);
? ? ? ? ? ? q1 = q1.next;
? ? ? ? } else if (q1.val < q2.val) {
? ? ? ? ? ? append(q1);
? ? ? ? ? ? q1 = q1.next;
? ? ? ? } else {
? ? ? ? ? ? append(q2);
? ? ? ? ? ? q2 = q2.next;
? ? ? ? }
? ? }
? ? return head;
}
void append(ListNode node) {
? ? if (head == null) {
? ? ? ? head = node;
? ? ? ? tail = node;
? ? } else {
? ? ? ? tail.next = node;
? ? ? ? tail = node;
? ? }
}
總結(jié)
鏈表排序問題并不難，但是作為綜合題，考察的是方方面面的知識(shí)。我們需要理解鏈表遍歷框架、鏈表快慢指針這些基本操作，還需要清除鏈表的性質(zhì)，選擇合適的排序算法，并從已有的數(shù)組排序方法中遷移知識(shí)。如果你要準(zhǔn)備面試的話，不妨把這道題做熟練了，對(duì)于鏈表類問題是一個(gè)很好的總結(jié)。
相關(guān)文章：
