超詳細教程，立馬學會連結清單解題

PS：本文是長篇技術文，注意安排時間閱讀 。

前言

如果說資料結構是算法的基礎，那麼數組和連結清單就是資料結構的基礎。 因為像堆，棧，對，圖等比較複雜的數組結基本上都可以由數組和連結清單來表示，是以掌握數組和連結清單的基本操作十分重要。

今天就來看看連結清單的基本操作及其在面試中的常見解題思路,本文将從以下幾個點來講解連結清單的核心知識

1. 什麼是連結清單，連結清單的優缺點
2. 連結清單的表示及基本操作
3. 連結清單常見解題思路---翻轉
4. 連結清單常見解題思路---快慢指針

什麼是連結清單

相信大家已經開始迫不及待地想用連結清單解題了，不過在開始之前我們還是要先來溫習下連結清單的定義，以及它的優勢與劣勢，磨刀不誤砍柴功！

連結清單的定義

連結清單是實體存儲單元上非連續的、非順序的存儲結構，它是由一個個結點，通過指針來聯系起來的，其中每個結點包括資料和指針。

連結清單的非連續，非順序，對應數組的連續，順序，我們來看看整型數組 1，2，3，4 在記憶體中是如何表示的

可以看到數組的每個元素都是連續緊鄰配置設定的，這叫連續性，同時由于數組的元素占用的大小是一樣的，在 Java 中 int 型大小固定為 4 個位元組,是以如果數組的起始位址是 100， 由于這些元素在記憶體中都是連續緊鄰配置設定的，大小也一樣，可以很容易地找出數組中任意一個元素的位置，比如數組中的第三個元素起始位址為 100 + 2 * 4 = 108,這就叫順序性。查找的時間複雜度是O(1),效率很高！

那連結清單在記憶體中是怎麼表示的呢

可以看到每個結點都配置設定在非連續的位置，結點與結點之間通過指針連在了一起，是以如果我們要找比如值為 3  的結點時，隻能通過結點 1 從頭到尾周遊尋找，如果元素少還好，如果元素太多（比如超過一萬個），每個元素的查找都要從頭開始查找，時間複雜度是O(n)，比起數組的 O(1)，差距不小。

除了查找性能連結清單不如數組外，還有一個優勢讓數組的性能高于連結清單,這裡引入程式局部性原理，啥叫程式局部性原理。

我們知道 CPU 運作速度是非常快的，如果 CPU 每次運算都要到記憶體裡去取資料無疑是很耗時的，是以在 CPU 與記憶體之間往往內建了挺多層級的緩存，這些緩存越接近CPU，速度越快，是以如果能提前把記憶體中的資料加載到如下圖中的 L1, L2, L3 緩存中，那麼下一次 CPU 取數的話直接從這些緩存裡取即可，能讓CPU執行速度加快，那什麼情況下記憶體中的資料會被提前加載到 L1,L2,L3 緩存中呢，答案是當某個元素被用到的時候，那麼這個元素位址附近的的元素會被提前加載到緩存中

以上文整型數組 1，2，3，4為例，當程式用到了數組中的第一個元素（即 1）時，由于 CPU 認為既然 1 被用到了，那麼緊鄰它的元素 2，3，4 被用到的機率會很大，是以會提前把 2，3，4 加到 L1,L2,L3 緩存中去，這樣 CPU 再次執行的時候如果用到 2，3，4，直接從 L1,L2,L3 緩存裡取就行了，能提升不少性能

畫外音：如果把CPU的一個時種看成一秒，則從 L1 讀取資料需要 3 秒，從 L2 讀取需要 11 秒，L3讀取需要 25秒，而從記憶體讀取呢，需要 1 分 40 秒，是以程式局部性原理能對 CPU 執行性能有很大的提升

而連結清單呢，由于連結清單的每個結點在記憶體裡都是随機分布的，隻是通過指針聯系在一起，是以這些結點的位址并不相鄰，自然無法利用 程式局部性原理 來提前加載到 L1,L2,L3 緩存中來提升程式性能。

畫外音：程式局部性原理是計算機中非常重要的原理，這裡不做展開，建議大家查閱相關資料詳細了解一下

如上所述，相比數組，連結清單的非連續，非順序确實讓它在性能上處于劣勢，那什麼情況下該使用連結清單呢？考慮以下情況

• 大記憶體空間配置設定

由于數組空間的連續性，如果要為數組配置設定 500M 的空間，這 500M 的空間必須是連續的，未使用的，是以在記憶體空間的配置設定上數組的要求會比較嚴格，如果記憶體碎片太多，配置設定連續的大空間很可能導緻失敗。而連結清單由于是非連續的，是以這種情況下選擇連結清單更合适。

• 元素頻繁删除和插入

如果涉及到元素的頻繁删除和插入，用連結清單就會高效很多，對于數組來說，如果要在元素間插入一個元素，需要把其餘元素一個個往後移（如圖示），以為新元素騰空間（同理，如果是删除則需要把被删除元素之後的元素一個個往前移），效率上無疑是比較低的。

(在 1，2 間插入 5，需要把2，3，4 同時往後移一位)

而連結清單的插入删除相對來說就比較簡單了，修改指針位置即可，其他元素無需做任何移動操作（如圖示：以插入為例）

綜上所述：如果資料以查為主，很少涉及到增和删，選擇數組，如果資料涉及到頻繁的插入和删除，或元素所需配置設定空間過大，傾向于選擇連結清單。

說了這麼多理論，相信讀者對數組和連結清單的差別應該有了更深刻地認識了，尤其是 程式局部性原理，是不是開了不少眼界^_^，如果面試中問到數組和連結清單的差別能回答到程式局部性原理，會是一個非常大的亮點！

接下來我們來看看連結清單的表現形式和解題技巧

需要說明的是有些代碼像列印連結清單等限于篇幅的關系沒有在文中展示，我把文中所有相關代碼都放到 github 中了，大家如果需要，可以通路我的 github 位址: https://github.com/allentofight/algorithm ，文中所有代碼均已用 Java 實作并運作通過

連結清單的表示

由于連結清單的特點（查詢或删除元素都要從頭結點開始）,是以我們隻要在連結清單中定義頭結點即可,另外如果要頻繁用到連結清單的長度，還可以額外定義一個變量來表示。

需要注意的是這個頭結點的定義是有講究的，一般來說頭結點有兩種定義形式，一種是直接以某個元素結點為頭結點,如下

一種是以一個虛拟的節點作為頭結點，即我們常說的哨兵，如下

定義這個哨兵有啥好處呢，假設我們不定義這個哨兵，來看看連結清單及添加元素的基本操作怎麼定義的

/**
* 連結清單中的結點，data代表節點的值，next是指向下一個節點的引用
 */
class Node {
int data;// 結點的數組域，值
    Node next = null;// 節點的引用，指向下一個節點
public Node(int data) {
this.data = data;
    }
}

/**
* 連結清單
 */
public class LinkedList {
int length = 0; // 連結清單長度，非必須，可不加
    Node head = null; // 頭結點

public void addNode(int val) {
if (head == null) {
            head = new Node(val);
        } else {
            Node tmp = head;
while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = new Node(val);
        }
    }
}
           

發現問題了嗎，注意看下面代碼

有兩個問題：

1. 每插入一個元素都要對頭結點進行判空比較，如果一個連結清單有很多元素需要插入，就需要進行很多次的判空處理，不是那麼高效
2. 頭結點與其他結點插入邏輯不統一（一個需要判空後再插入，一個不需要判空直接插入）,從程式邏輯性來說不是那麼合理（因為結點與結點是平級，添加邏輯理應相同）

如果定義了哨兵結點，以上兩個問題都可解決，來看下使用哨兵結點的連結清單定義

public class LinkedList {
int length = 0; // 連結清單長度，非必須，可不加
    Node head = new Node(0); // 哨兵結點
public void addNode(int val) {
        Node tmp = head;
while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = new Node(val);
        length++
    }
}
           

可以看到，定義了哨兵結點的連結清單邏輯上清楚了很多,不用每次插入元素都對頭結點進行判空，也統一了每一個結點的添加邏輯。

是以之後的習題講解中我們使用的連結清單都是使用定義了哨兵結點的形式。

做了這麼多前期的準備工作，終于要開始我們的正餐了：連結清單解題常用套路--翻轉！

連結清單常見解題套路--翻轉

熱身賽

既然我們要用連結清單解題，那我們首先就構造一個連結清單吧 題目：給定數組 1，2，3，4 構造成如下連結清單 head-->4---->3---->2---->1

看清楚了，是逆序構造連結清單！順序構造我們都知道怎麼構造，對每個元素持續調用上文代碼定義的 addNode 方法即可（即尾插法），與尾插法對應的，是頭插法，即把每一個元素插到頭節點後面即可，這樣就能做到逆序構造連結清單，如圖示（以插入1，2 為例）

頭插法比較簡單，直接上代碼,直接按以上動圖的步驟來完成邏輯，如下

public class LinkedList {
int length = 0; // 連結清單長度，非必須，可不加
    Node head = new Node(0); // 哨兵節點

// 頭插法
public void headInsert(int val) {
// 1.構造新結點
        Node newNode = new Node(val);
// 2.新結點指向頭結點之後的結點
        newNode.next = head.next;
// 3.頭結點指向新結點
        head.next = newNode;
        length++
    }

public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
int[] arr = {1,2,3,4};
// 頭插法構造連結清單
for (int i = 0; i < arr.length; i++) {
            linkedList.headInsert(arr[i]);
        }
// 列印連結清單,将列印 4-->3-->2-->1
        linkedList.printList();
    }
}
           

小試牛刀

現在我們加大一下難度，來看下曾經的 Google 面試題： 給定單向連結清單的頭指針和一個節點指針，定義一個函數在 O(1) 内删除這個節點。

如圖示：即給定值為 2 的結點，如何把 2 給删了。

我們知道，如果給定一個結點要删除它的後繼結點是很簡單的，隻要把這個結點的指針指向後繼結點的後繼結點即可

如圖示：給定結點 2，删除它的後繼結點 3， 把結點 2 的 next 指針指向 3 的後繼結點 4 即可。

但給定結點 2，該怎麼删除結點 2 本身呢，注意題目沒有規定說不能改變結點中的值，是以有一種很巧妙的方法，狸貓換太子！我們先通過結點 2 找到結點 3，再把節點 3 的值賦給結點 2，此時結點 2 的值變成了 3，這時候問題就轉化成了上圖這種比較簡單的需求，即根據結點 2 把結點 3 移除即可，看圖

不過需要注意的是這種解題技巧隻适用于被删除的指定結點是中間結點的情況，如果指定結點是尾結點，還是要老老實實地找到尾結點的前繼結點，再把尾結點删除，代碼如下

/**
 * 删除指定的結點
 * @param deletedNode
 */
public void removeSelectedNode(Node deletedNode) {
// 如果此結點是尾結點我們還是要從頭周遊到尾結點的前繼結點，再将尾結點删除
if (deletedNode.next == null) {
        Node tmp = head;
while (tmp.next != deletedNode) {
            tmp = tmp.next;
        }
// 找到尾結點的前繼結點，把尾結點删除
        tmp.next = null;
    } else {
        Node nextNode = deletedNode.next;
// 将删除結點的後繼結點的值賦給被删除結點
        deletedNode.data = nextNode.data;
// 将 nextNode 結點删除
        deletedNode.next = nextNode.next;
        nextNode.next = null;
    }
}
           

入門到進階:連結清單翻轉

接下來我們會重點看一下連結清單的翻轉，連結清單的翻轉可以衍生出很多的變形，是面試中非常熱門的考點，基本上考連結清單必考翻轉！是以掌握連結清單的翻轉是必修課！

什麼是連結清單的翻轉:給定連結清單 head-->4--->3-->2-->1，将其翻轉成 head-->1-->2-->3-->4 ，由于翻轉連結清單是如此常見，如此重要，是以我們分别詳細講解下如何用遞歸和非遞歸這兩種方式來解題

• 遞歸翻轉

關于遞歸的文章之前寫了三篇，如果之前沒讀過的，強烈建議點選這裡檢視，總結了遞歸的常見解題套路,給出了遞歸解題的常見四步曲，如果看完對以下遞歸的解題套路會更加深刻，這裡不做贅述了，我們直接套遞歸的解題思路：

首先我們要檢視翻轉連結清單是否符合遞歸規律：問題可以分解成具有相同解決思路的子問題，子子問題...，直到最終的子問題再也無法分解。

要翻轉 head--->4--->3-->2-->1 連結清單，不考慮 head 結點，分析 4--->3-->2-->1，仔細觀察我們發現隻要先把 3-->2-->1 翻轉成 3<----2<----1，之後再把 3 指向 4 即可（如下圖示）

圖：翻轉連結清單主要三步驟

隻要按以上步驟定義好這個翻轉函數的功能即可， 這樣由于子問題與最初的問題具有相同的解決思路，拆分後的子問題持續調用這個翻轉函數即可達到目的。

注意看上面的步驟1，問題的規模是不是縮小了（如下圖），從翻轉整個連結清單變成了隻翻轉部分連結清單！問題與子問題都是從某個結點開始翻轉，具有相同的解決思路，另外當縮小到隻翻轉一個結點時，顯然是終止條件，符合遞歸的條件！之後的翻轉 3-->2-->1, 2-->1 持續調用這個定義好的遞歸函數即可！

既然符合遞歸的條件，那我們就可以套用遞歸四步曲來解題了（注意翻轉之後 head 的後繼節點變了，需要重新設定！别忘了這一步）

1、定義遞歸函數,明确函數的功能 根據以上分析，這個遞歸函數的功能顯然是翻轉某個節點開始的連結清單，然後傳回新的頭結點

/**
 * 翻轉結點 node 開始的連結清單
 */
public Node invertLinkedList(Node node) {
}
           

2、尋找遞推公式 上文中已經詳細畫出了翻轉連結清單的步驟，簡單總結一下遞推步驟如下

• 針對結點 node (值為 4), 先翻轉 node 之後的結點   invert(node->next) ,翻轉之後 4--->3--->2--->1 變成了 4--->3<---2<---1
• 再把 node 節點的下個節點（3）指向 node，node 的後繼節點設定為空（避免形成環），此時變成了 4<---3<---2<---1
• 傳回新的頭結點，因為此時新的頭節點從原來的 4 變成了 1，需要重新設定一下 head

3、将遞推公式代入第一步定義好的函數中，如下 (invertLinkedList)

/**
 * 遞歸翻轉結點 node 開始的連結清單
 */
public Node invertLinkedList(Node node) {
if (node.next == null) {
return node;
    }

// 步驟 1: 先翻轉 node 之後的連結清單
    Node newHead = invertLinkedList(node.next);

// 步驟 2: 再把原 node 節點後繼結點的後繼結點指向 node (4)，node 的後繼節點設定為空(防止形成環)
    node.next.next = node;
    node.next = null;

// 步驟 3: 傳回翻轉後的頭結點
return newHead;
}

public static void main(String[] args) {
    LinkedList linkedList = new LinkedList();
int[] arr = {4,3,2,1};
for (int i = 0; i < arr.length; i++) {
        linkedList.addNode(arr[i]);
    }
    Node newHead = linkedList.invertLinkedList(linkedList.head.next);
// 翻轉後别忘了設定頭結點的後繼結點！
    linkedList.head.next = newHead;
    linkedList.printList();      // 列印 1，2，3，4
}
           

畫外音：翻轉後由于 head 的後繼結點變了，别忘了重新設定哦！

4、計算時間/空間複雜度 由于遞歸調用了 n 次 invertLinkedList 函數，是以時間複雜度顯然是 O(n), 空間複雜度呢，沒有用到額外的空間，但是由于遞歸調用了  n 次 invertLinkedList 函數，壓了 n 次棧，是以空間複雜度也是 O(n)。

遞歸一定要從函數的功能去了解，從函數的功能看，定義的遞歸函數清晰易懂，定義好了之後，由于問題與被拆分的子問題具有相同的解決思路，是以子問題隻要持續調用定義好的功能函數即可，切勿層層展開子問題，此乃遞歸常見的陷阱！仔細看函數的功能，其實就是按照下圖實作的。(對照着代碼看，是不是清晰易懂^_^)

• 非遞歸翻轉連結清單（疊代解法）

我們知道遞歸比較容易造成棧溢出，是以如果有其他時間/空間複雜度相近或更好的算法，應該優先選擇非遞歸的解法,那我們看看如何用疊代來翻轉連結清單，主要思路如下

步驟 1： 定義兩個節點：pre, cur ，其中 cur 是 pre 的後繼結點，如果是首次定義， 需要把 pre 指向 cur 的指針去掉，否則由于之後連結清單翻轉，cur 會指向 pre， 就進行了一個環(如下)，這一點需要注意

步驟2：知道了 cur 和 pre,翻轉就容易了，把 cur 指向 pre 即可，之後把 cur 設定為 pre ，cur 的後繼結點設定為 cur 一直往前重複此步驟即可,完整動圖如下

注意：同遞歸翻轉一樣，疊代翻轉完了之後 head 的後繼結點從 4 變成了 1，記得重新設定一下。

知道了解題思路，實作代碼就容易多了，直接上代碼

/**
 * 疊代翻轉
 */
public void iterationInvertLinkedList() {
// 步驟 1
    Node pre = head.next;
    Node cur = pre.next;
    pre.next = null;

while (cur != null) {
/**
         * 務必注意：在 cur 指向 pre 之前一定要先保留 cur 的後繼結點，不然 cur 指向 pre 後就再也找不到後繼結點了
         * 也就無法對 cur 後繼之後的結點進行翻轉了
         */
        Node next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
// 此時 pre 為頭結點的後繼結點
    head.next = pre;
}
           

用疊代的思路來做由于循環了 n 次，顯然時間複雜度為 O(n),另外由于沒有額外的空間使用，也未像遞歸那樣調用遞歸函數不斷壓棧，是以空間複雜度是 O(1),對比遞歸，顯然應該使用疊代的方式來處理！

花了這麼大的精力我們總算把翻轉連結清單給搞懂了，如果大家看了之後幾道翻轉連結清單的變形，會發現我們花了這麼大篇幅講解翻轉連結清單是值得的。

接下來我們來看看連結清單翻轉的變形

變形題 1： 給定一個連結清單的頭結點 head,以及兩個整數 from 和 to ,在連結清單上把第 from 個節點和第 to 個節點這一部分進行翻轉。 例如：給定如下連結清單，from = 2, to = 4 head-->5-->4-->3-->2-->1 将其翻轉後，連結清單變成 head-->5--->2-->3-->4-->1

有了之前翻轉整個連結清單的解題思路，現在要翻轉部分連結清單就相對簡單多了,主要步驟如下:

1. 根據 from 和 to 找到 from-1, from, to,  to+1 四個結點(注意臨界條件，如果 from 從頭結點開始，則 from-1 結點為空, 翻轉後需要把 to 設定為頭結點的後繼結點， from 和 to 結點也可能超過尾結點,這兩種情況不符合條件不翻轉)。
2. 對 from 到 to 的結點進行翻轉
3. 将 from-1 節點指向 to 結點，将 from 結點指向 to + 1 結點

知道了以上的思路，代碼就簡單了,按上面的步驟1，2，3 實作，注釋也寫得很詳細，看以下代碼（對 from 到 to 結點的翻轉我們使用疊代翻轉，當然使用遞歸也是可以的，限于篇幅關系不展開，大家可以嘗試一下）。

/**
 * 疊代翻轉 from 到 to 的結點
 */
public void iterationInvertLinkedList(int fromIndex, int toIndex) throws Exception {

    Node fromPre = null;            // from-1結點
    Node from = null;               // from 結點
    Node to = null;                 // to 結點
    Node toNext = null;             // to+1 結點

// 步驟 1：找到  from-1, from, to,  to+1 這四個結點
    Node tmp = head.next;
int curIndex = 1;      // 頭結點的index為1
while (tmp != null) {
if (curIndex == fromIndex-1) {
            fromPre = tmp;
        } else if (curIndex == fromIndex) {
            from = tmp;
        } else if (curIndex == toIndex) {
            to = tmp;
        } else if (curIndex == toIndex+1) {
            toNext = tmp;
        }
        tmp = tmp.next;
        curIndex++;
    }

if (from == null || to == null) {
// from 或 to 都超過尾結點不翻轉
throw new Exception("不符合條件");
    }

// 步驟2：以下使用循環疊代法翻轉從 from 到 to 的結點
    Node pre = from;
    Node cur = pre.next;
while (cur != toNext) {
        Node next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }

// 步驟3：将 from-1 節點指向 to 結點（如果從 head 的後繼結點開始翻轉，則需要重新設定 head 的後繼結點），将 from 結點指向 to + 1 結點
if (fromPre != null) {
        fromPre.next = to;
    } else {
        head.next = to;
    }
    from.next = toNext;
}
           

變形題 2： 給出一個連結清單，每 k 個節點一組進行翻轉，并傳回翻轉後的連結清單。k 是一個正整數，它的值小于或等于連結清單的長度。如果節點總數不是 k 的整數倍，那麼将最後剩餘節點保持原有順序。

示例 : 給定這個連結清單：head-->1->2->3->4->5 當 k = 2 時，應當傳回: head-->2->1->4->3->5 當 k = 3 時，應當傳回: head-->3->2->1->4->5 說明 :

• 你的算法隻能使用常數的額外空間。
• 你不能隻是單純的改變節點内部的值，而是需要實際的進行節點交換。

這道題是 LeetCode 的原題,屬于 hard 級别，如果這一題你懂了，那對連結清單的翻轉應該基本沒問題了，有了之前的翻轉連結清單基礎，相信這題不難。

隻要我們能找到翻一組 k 個結點的方法，問題就解決了（之後隻要重複對 k 個結點一組的連結清單進行翻轉即可）。

接下來，我們以以下連結清單為例

來看看怎麼翻轉 3 個一組的連結清單（此例中 k = 3）

• 首先，我們要記錄 3 個一組這一段連結清單的前繼結點,定義為 startKPre,然後再定義一個 step, 從這一段的頭結點 (1）開始周遊 2 次，找出這段連結清單的起始和終止結點，如下圖示

  

• 找到 startK 和 endK 之後，根據之前的疊代翻轉法對 startK 和 endK 的這段連結清單進行翻轉

  

• 然後将 startKPre 指向 endK,将 startK 指向 endKNext，即完成了對 k 個一組結點的翻轉。

  

知道了一組 k 個怎麼翻轉，之後隻要重複對 k 個結點一組的連結清單進行翻轉即可，對照圖示看如下代碼應該還是比較容易了解的

/**
 * 每 k 個一組翻轉連結清單
 * @param k
 */
public void iterationInvertLinkedListEveryK(int k) {
    Node tmp = head.next;
int step = 0;               // 計數，用來找出首結點和尾結點

    Node startK = null;         // k個一組連結清單中的頭結點
    Node startKPre = head;      // k個一組連結清單頭結點的前置結點
    Node endK;                  // k個一組連結清單中的尾結點
while (tmp != null) {
// tmp 的下一個節點,因為由于翻轉，tmp 的後繼結點會變,要提前儲存
        Node tmpNext = tmp.next;
if (step == 0) {
// k 個一組連結清單區間的頭結點
            startK = tmp;
            step++;
        } else if (step == k-1) {
// 此時找到了 k 個一組連結清單區間的尾結點（endK）,對這段連結清單用疊代進行翻轉
            endK = tmp;
            Node pre = startK;
            Node cur = startK.next;
if (cur == null) {
break;
            }
            Node endKNext = endK.next;
while (cur != endKNext) {
                Node next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }
// 翻轉後此時 endK 和 startK 分别是是 k 個一組連結清單中的首尾結點
            startKPre.next = endK;
            startK.next = endKNext;

// 目前的 k 個一組翻轉完了，開始下一個 k 個一組的翻轉
            startKPre = startK;
            step = 0;
        } else {
            step++;
        }
        tmp = tmpNext;
    }
}
           

時間複雜度是多少呢，對連結清單從頭到尾循環了 n 次，同時每 k 個結點翻轉一次，可以認為總共翻轉了 n 次，是以時間複雜度是O(2n),去掉常數項，即為 O(n)。 注：這題時間複雜度比較誤認為是O(k * n),實際上并不是每一次連結清單的循環都會翻轉連結清單，隻是在循環連結清單元素每 k 個結點的時候才會翻轉

變形3: 變形 2 針對的是順序的 k 個一組翻轉，那如何逆序 k 個一組進行翻轉呢

例如：給定如下連結清單， head-->1-->2-->3-->4-->5 逆序 k 個一組翻轉後，連結清單變成（k = 2 時） head-->1--->3-->2-->5-->4

這道題是位元組跳動的面試題，确實夠變态的，順序 k 個一組翻轉都已經屬于 hard 級别了，逆序 k 個一組翻轉更是屬于 super hard 級别了，不過其實有了之前知識的鋪墊，應該不難，隻是稍微變形了一下，隻要對連結清單做如下變形即可

代碼的每一步其實都是用了我們之前實作好的函數，是以我們之前做的每一步都是有伏筆的哦！就是為了解決位元組跳動這道終極面試題！

/**
 * 逆序每 k 個一組翻轉連結清單
 * @param k
 */
public void reverseIterationInvertLinkedListEveryK(int k) {
// 先翻轉連結清單
    iterationInvertLinkedList();
// k 個一組翻轉連結清單
    iterationInvertLinkedListEveryK(k);
// 再次翻轉連結清單
    iterationInvertLinkedList();
}
           

由此可見，掌握基本的連結清單翻轉非常重要！難題多是在此基礎了做了相應的變形而已

連結清單解題利器---快慢指針

快慢指針在面試中出現的機率也很大，也是務必要掌握的一個要點，本文總結了市面上常見的快慢指針解題技巧，相信看完後此類問題能手到擒來。本文将詳細講述如何用快慢指針解決以下兩大類問題

1. 尋找/删除第 K 個結點
2. 有關連結清單環問題的相關解法

小試牛刀之一

LeetCode 876：給定一個帶有頭結點 head 的非空單連結清單，傳回連結清單的中間結點。如果有兩個中間結點，則傳回第二個中間結點。

解法一

要知道連結清單的中間結點，首先我們需要知道連結清單的長度，說到連結清單長度大家想到了啥，還記得我們在上文中說過哨兵結點可以儲存連結清單的長度嗎，這樣直接 從 head 的後繼結點 開始周遊  連結清單長度 / 2 次即可找到中間結點。為啥中間結點是 連結清單長度/2，我們仔細分析一下

1. 假如連結清單長度是奇數: head--->1--->2--->3--->4--->5, 從 1 開始周遊 5/2 = 2 （取整）次，到達 3，3确實是中間結點
2. 假如連結清單長度是偶數: head--->1--->2--->3--->4--->5--->6, 從 1 開始周遊 6/2 = 3次，到達 4，4 确實是中間結點的第二個結點

畫外音：多畫畫圖，舉舉例，能看清事情的本質！

哨後結點的長度派上用場了，這種方式最簡單，直接上代碼

public Node findMiddleNode() {
    Node tmp = head.next;
int middleLength = length / 2;
while (middleLength > 0) {
        tmp = tmp.next;
        middleLength--;
    }
return tmp;
}
           

解法二

如果哨兵結點裡沒有定義長度呢，那就要周遊一遍連結清單拿到連結清單長度（定義為 length）了，然後再從頭結點開始周遊 length / 2 次即為中間結點

public Node findMiddleNodeWithoutHead() {
    Node tmp = head.next;
int length = 1;
// 選周遊一遍拿到連結清單長度
while (tmp.next != null) {
        tmp = tmp.next;
        length++;
    }

// 再周遊一遍拿到連結清單中間結點
    tmp = head.next;
int middleLength = length / 2;
while (middleLength > 0) {
        tmp = tmp.next;
        middleLength--;
    }
return tmp;
}
           

解法三

解法二由于要周遊兩次連結清單，顯得不是那麼高效，那能否隻周遊一次連結清單就能拿到中間結點呢。

這裡就引入我們的快慢指針了，主要有三步 1、 快慢指針同時指向 head 的後繼結點 2、 慢指針走一步，快指針走兩步 3、 不斷地重複步驟2，什麼時候停下來呢，這取決于連結清單的長度是奇數還是偶數

• 如果連結清單長度為奇數,當 fast.next = null 時,slow 為中間結點

  

• 如果連結清單長度為偶數,當 fast = null 時,slow 為中間結點

  

  由以上分析可知:當 fast = null 或者 fast.next = null 時，此時的 slow 結點即為我們要求的中間結點,否則不斷地重複步驟 2， 知道了思路，代碼實作就簡單了

/**
 * 使用快慢指針查找找到中間結點
 * @return
 */
public Node findMiddleNodeWithSlowFastPointer() {
    Node slow = head.next;
    Node fast = head.next;
while (fast != null && fast.next != null) {
// 快指針走兩步
        fast = fast.next.next;
// 慢指針走一步
        slow = slow.next;
    }
// 此時的 slow 結點即為哨兵結點
return slow;
}
           

有了上面的基礎，我們現在再大一下難度，看下下面這道題

輸入一個連結清單，輸出該連結清單中的倒數第 k 個結點。比如連結清單為 head-->1-->2-->3-->4-->5。求倒數第三個結點（即值為 3 的節點）

分析：我們知道如果要求順序的第 k 個結點還是比較簡單的，從 head 開始周遊 k 次即可，如果要求逆序的第 k 個結點，正常的做法是先順序周遊一遍連結清單，拿到連結清單長度，然後再周遊 連結清單長度-k 次即可，這樣要周遊兩次連結清單，不是那麼高效，如何隻周遊一次呢，還是用我們的說的快慢指針解法

1. 首先讓快慢指針同時指向 head 的後繼結點
2. 快指針往前走 k- 1 步,先走到第 k 個結點
3. 快慢指針同時往後走一步，不斷重複此步驟，直到快指針走到尾結點,此時的 slow 結點即為我們要找的倒序第 k 個結點

注：需要注意臨界情況：k 大于連結清單的長度，這種異常情況應該抛異常

public Node findKthToTail(int k) throws Exception {
    Node slow = head.next;
    Node fast = head.next;

// 快指針先移到第k個結點
int tmpK = k - 1;
while (tmpK > 0 && fast != null) {
        fast = fast.next;
        tmpK--;
    }
// 臨界條件：k大于連結清單長度
if (fast == null) {
throw new Exception("K結點不存在異常");
    }
// slow 和 fast 同時往後移，直到 fast 走到尾結點
while (fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
return slow;
}
           

知道了如何求倒序第 k 個結點，再來看看下面這道題

給定一個單連結清單，設計一個算法實作連結清單向右旋轉 K 個位置。舉例： 給定 head->1->2->3->4->5->NULL, K=3,右旋後即為 head->3->4->5-->1->2->NULL

分析：這道題其實是對求倒序第 K 個位置的的一個變形，主要思路如下

• 先找到倒數第 K+1 個結點, 此結點的後繼結點即為倒數第 K 個結點
• 将倒數第 K+1 結點的的後繼結點設定為 null
• 将 head 的後繼結點設定為以上所得的倒數第 K 個結點，将原尾結點的後繼結點設定為原 head 的後繼結點

public void reversedKthToTail(int k) throws Exception {
// 直接調已實作的 尋找倒序k個結點的方法，這裡是 k+1
    Node KPreNode = findKthToTail(k+1);
// 倒數第 K 個結點
    Node kNode = KPreNode.next;
    Node headNext = head.next;

    KPreNode.next = null;
    head.next = kNode;

// 尋找尾結點
    Node tmp = kNode;
while (tmp.next != null) {
        tmp = tmp.next;
    }
// 尾結點的後繼結點設定為原 head 的後繼結點
    tmp.next = headNext;
}
           

有了上面兩道題的鋪墊，相信下面這道題不是什麼難事，限于篇幅關系，這裡不展開，大家可以自己試試

輸入一個連結清單，删除該連結清單中的倒數第 k 個結點

小試牛刀之二

判斷兩個單連結清單是否相交及找到第一個交點,要求空間複雜度 O(1)。 如圖示：如果兩個連結清單相交，5為這兩個連結清單相交的第一個交點

畫外音：如果沒有空間複雜度O(1)的限制，其實有多種解法，一種是周遊連結清單 1，将連結清單 1 的所有的結點都放到一個 set 中，再次周遊連結清單 2，每周遊一個結點，就判斷這個結點是否在 set，如果發現結點在這個 set 中，則這個結點就是連結清單第一個相交的結點

分析：首先我們要明白，由于連結清單本身的性質，如果有一個結點相交，那麼相交結點之後的所有結點都是這兩個連結清單共用的，也就是說兩個連結清單的長度主要相差在相交結點之前的結點長度，于是我們有以下思路

1、如果連結清單沒有定義長度，則我們先周遊這兩個連結清單拿到兩個連結清單長度，假設分别為 L1, L2 (L1 >= L2), 定義 p1, p2 指針分别指向各自連結清單 head 結點，然後 p1 先往前走 L1 - L2 步。這一步保證了 p1，p2 指向的指針與相交結點(如果有的話)一樣近。

2、 然後 p1,p2 不斷往後周遊，每次走一步，邊周遊邊判斷相應結點是否相等，如果相等即為這兩個連結清單的相交結點

public static Node detectCommonNode(LinkedList list1, LinkedList list2) {
int length1 = 0;        // 連結清單 list1 的長度
int length2 = 0;        // 連結清單 list2 的長度

    Node p1 = list1.head;
    Node p2 = list2.head;

while (p1.next != null) {
        length1++;
        p1 = p1.next;
    }

while (p2.next != null) {
        length2++;
        p2 = p2.next;
    }

    p1 = list1.head;
    p2 = list2.head;

// p1 或 p2 前進 |length1-length2| 步
if (length1 >= length2) {
int diffLength = length1-length2;
while (diffLength > 0) {
            p1 = p1.next;
            diffLength--;
        }
    } else {
int diffLength = length2-length1;
while (diffLength > 0) {
            p2 = p2.next;
            diffLength--;
        }
    }
// p1,p2分别往後周遊，邊周遊邊比較，如果相等，即為第一個相交結點
while (p1 != null && p2.next != null) {
        p1 = p1.next;
        p2 = p2.next;
if (p1.data == p2.data) {
// p1，p2 都為相交結點，傳回 p1 或 p2
return p1;
        }
    }
// 沒有相交結點，傳回空指針
return null;
}
           

進階

接下來我們來看如何用快慢指針來判斷連結清單是否有環,這是快慢指針最常見的用法

判斷連結清單是否有環，如果有，找到環的入口位置（下圖中的 2），要求空間複雜度為O(1)

首先我們要看如果連結清單有環有什麼規律，如果從 head 結點開始周遊，則這個周遊指針一定會在以上的環中繞圈子，是以我們可以分别定義快慢指針，慢指針走一步，快指針走兩步， 由于最後快慢指針在周遊過程中一直會在圈中裡繞，且快慢指針每次的周遊步長不一樣，是以它們在裡面不斷繞圈子的過程一定會相遇，就像 5000 米長跑，一人跑的快，一人快的慢，跑得快的人一定會追上跑得慢的（即套圈）。

還不明白？那我們簡單證明一下

1、 假如快指針離慢指針相差一個結點,則再一次周遊，慢指針走一步，快指針走兩步，相遇

2、  假如快指針離慢指針相差兩個結點,則再一次周遊，慢指針走一步，快指針走兩步，相差一個結點，轉成上述 1 的情況

3、 假如快指針離慢指針相差 N 個結點（N大于2），則下一次周遊由于慢指針走一步，快指針走兩步，是以相差 N+1-2 = N-1 個結點，發現了嗎，相差的結點從 N 變成了 N-1,縮小了！不斷地周遊，相差的結點會不斷地縮小，當 N 縮小為 2 時，即轉為上述步驟 2 的情況，由此得證，如果有環，快慢指針一定會相遇！

畫外音：如果慢指針走一步，快指針走的不是兩步，而是大于兩步，會有什麼問題，大家可以考慮一下

/**
 * 判斷是否有環,傳回快慢指針相遇結點,否則傳回空指針
 */
public Node detectCrossNode() {
    Node slow = head;
    Node fast = head;

while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;

if (fast == null) {
return null;
        }

if (slow.data == fast.data) {
return slow;
        }
    }
return  null;
}
           

判斷有環為啥要傳回相遇的結點，而不是傳回 true 或 false 呢。 因為題目中還有一個要求，判斷環的入口位置，就是為了這個做鋪墊的,一起來看看怎麼找環的入口，需要一些分析的技巧

假設上圖中的 7 為快慢指針相遇的結點，不難看出慢指針走了 L + S 步，快指針走得比慢指針更快，它除了走了 L + S 步外，還額外在環裡繞了 n  圈，是以快指針走了 L+S+nR 步（R為圖中環的長度）,另外我們知道每周遊一次，慢指針走了一步，快指針走了兩步，是以快指針走的路程是慢指針的兩倍,即 2 (L+S) = L+S+nR，即  L+S = nR

• 當 n = 1 時，則 L+S = R 時,則從相遇點 7 開始周遊走到環入口點 2 的距離為 R - S = L，剛好是環的入口結點,而 head 與環入口點 2 的距離恰好也為 L，是以隻要在頭結點定義一個指針，在相遇點（7）定義另外一個指針，兩個指針同時周遊，每次走一步，必然在環的入口位置 2 相遇
• 當 n > 1 時，L + S = nR,即 L = nR - S,  nR-S 怎麼了解？可以看作是指針從結點  7 出發，走了 n 圈後，回退 S 步，此時剛好指向環入口位置，也就是說如果設定一個指針指向 head（定義為p1）, 另設一個指針指向 7（定義為p2），不斷周遊，p2 走了 nR-S 時（即環的入口位置），p1也剛好走到這裡（此時 p1 走了 nR-S =  L步，剛好是環入口位置），即兩者相遇！

綜上所述，要找到入口結點，隻需定義兩個指針，一個指針指向head, 一個指針指向快慢指向的相遇點，然後這兩個指針不斷周遊（同時走一步），當它們指向同一個結點時即是環的入口結點

public Node getRingEntryNode() {
// 擷取快慢指針相遇結點
        Node crossNode = detectCrossNode();

// 如果沒有相遇點，則沒有環
if (crossNode == null) {
return null;
        }

// 分别定義兩個指針，一個指向頭結點，一個指向相交結點
        Node tmp1 = head;
        Node tmp2 = crossNode;

// 兩者相遇點即為環的入口結點
while (tmp1.data != tmp2.data) {
            tmp1 = tmp1.next;
            tmp2 = tmp2.next;
        }
return tmp1;
    }
           

思考題：知道了環的入口結點，怎麼求環的長度？

總結

-END-