算法：鏈表

鏈表的技巧和操作總結

常用技巧：

鏈表中的常用操作

題目一：反轉一個單鏈表

題目二：鏈表的中間結點

題目三：返回倒數第k個結點

題目四：合并兩個有序鏈表

題目五：移除鏈表元素

題目六：鏈表分割

題目七：鏈表的回文結構

題目八：相交鏈表

題目九：環形鏈表I環形鏈表I

題目十：環形鏈表II

題目十一：隨機鏈表的復制

題目十二：兩數相加

題目十三：兩兩交換鏈表中的結點

題目十四：重排鏈表

題目十五：合并 k 個升序鏈表

題目十六：K 個一組翻轉鏈表

鏈表的技巧和操作總結

常用技巧：

畫圖

能畫圖就畫圖，直觀形象，比較容易我們理解

引入虛擬頭結點

因為題目中，大多數都是第一個節點就存儲的是有效元素了，這時就需要考慮許多的邊界情況，比較麻煩，所以我們可以引入一個虛擬的頭結點，即變為了帶哨兵位頭結點的鏈表

①便于我們處理邊界條件
②方便我們對鏈表進行操作

不吝嗇空間，大膽定義變量

例如有題是在A和B節點之間插入一個新結點C，此時按照往常的思維，會考慮先執行哪一步，才不會影響后面的操作，因為如果順序執行錯了，可能就找不到A后面的B結點了

那么這時，我們可以在操作前，提前定義一個變量next，讓它代表B結點，這樣無論我們怎么操作，都不會導致執行這步操作時，造成找不到B結點的情況

快慢雙指針

快慢雙指針，非常適合于判斷鏈表中是否有環、找鏈表中環的入口、找鏈表中倒數第n個結點

下面的前幾道題中，就有快慢雙指針的方式解決的題目

鏈表中的常用操作

①創建一個新結點

②尾插

③頭插（逆序鏈表）

在進行題目練習之前，需要知道，題目中所給的鏈表，每一個結點的結構都是如下所示的，直接使用即可：

struct ListNode 
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};

題目一：反轉一個單鏈表

給你單鏈表的頭節點?head?，請你反轉鏈表，并返回反轉后的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]
輸出：[2,1]

示例 3：

輸入：head = []
輸出：[]

解法一：頭插法

這里的反轉單鏈表是非常經典的頭插就可以解決問題，這里可以使用哨兵位頭結點也可以不使用，一般尾插時用哨兵位頭結點的情況比較多，頭插可以不用，具體看下面說明：

初始我們可以將head賦值給cur，再創建一個newhead的結點指針，為了防止將cur頭插到newhead后面時找不到原鏈表cur后面的結點了，所以還需要創建一個next的指針，指向cur后面的結點，初始情況如下：

所以接下來頭插的操作就是
創建next保存cur->next，cur->next = newhead，newhead = cur，cur = next，變為下圖的情況：

接下來依舊是進行上述操作：

以此類推...

不帶哨兵位的頭結點的代碼如下：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* newhead = nullptr;while(cur){ListNode* next = cur->next;//保存cur->nextcur->next = newhead;newhead = cur;cur = next;}return newhead;}
};

帶哨兵位的頭結點就不細說了，代碼如下：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* tail = new ListNode;//哨兵位頭結點tailtail->next = nullptr;while(cur){ListNode* next = cur->next;cur->next = tail->next;tail->next = cur;cur = next;}ListNode* del = tail;tail = tail->next;delete del;//釋放new出來的哨兵位頭結點return tail;}
};

解法二：指針的方向顛倒

指針方向顛倒的思想，如下所示：

最后返回val為3的結點指針即可，那么如何定義變量呢

首先需要一個cur指針指向當前的結點，需要一個prev指針指向前一個結點，便于方向指向，最后還需要一個next指針，指向cur之后的結點，避免找不到cur后面的結點

初始指向是這樣的：

需要先記錄cur的下一個結點next，再將cur指向prev，改變prev的指向到cur，再移動cur到next：

知道cur指向nullptr為止，此時位置信息如下：

此時返回prev即可

代碼如下：

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode* cur = head;ListNode* prev = nullptr;while(cur){ListNode* next = cur->next;//定義cur的下一個結點位置cur->next = prev; //指針顛倒prev = cur; //改變prev指向cur = next; //改變cur位置}return prev;}
};

題目二：鏈表的中間結點

給你單鏈表的頭結點?head?，請你找出并返回鏈表的中間結點。

如果有兩個中間結點，則返回第二個中間結點。

示例 1：

輸入：head = [1,2,3,4,5]
輸出：[3,4,5]
解釋：鏈表只有一個中間結點，值為 3 。

示例 2：

輸入：head = [1,2,3,4,5,6]
輸出：[4,5,6]
解釋：該鏈表有兩個中間結點，值分別為 3 和 4 ，返回第二個結點。

解法一：遍歷求個數

這道題就很典型了，有很多種解法，最簡單的就是先遍歷一遍得到鏈表的元素個數，除2得到該鏈表第幾個位置是中間數，然后第二次遍歷，遍歷到該結點時就return即可

代碼如下：

class Solution 
{
public:ListNode* middleNode(ListNode* head) {ListNode* cur = head;int num = 0;while(cur){num++;cur = cur->next;}int mid = num / 2 + 1;//得到中間值，不論奇數還是偶數個都適用cur = head;while(--mid)//--mid循環mid-1次，因為cur剛開始就指向第一個位置{cur = cur->next;}return cur;}
};

解法二：快慢指針

這道題就是典型的可以使用快慢指針的思想，定義兩個指針，一個slow一個fast

慢指針slow一次走一步，快指針fast一次走兩步，當快指針走到鏈表的結尾時，慢指針自然走到中間位置了

下面舉奇數個的例子，奇數個時判斷條件是fast->next為空：

下面是偶數個的例子，偶數個時判斷條件是fast為空：

這種快慢指針的方法，無論奇數個還是偶數個都能夠滿足題目要求

代碼如下：

class Solution 
{
public:ListNode* middleNode(ListNode* head) {ListNode* slow, *fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}
};

題目三：返回倒數第k個結點

實現一種算法，找出單向鏈表中倒數第 k 個節點。返回該節點的值。

示例：

輸入： 1->2->3->4->5 和 k = 2
輸出： 4

說明：

給定的?k?保證是有效的。

解法一：求鏈表的長度

解法一依舊是求鏈表的長度num，題目要求是倒數第k個，所以找正數的第num-k+1個，這種方式比較簡單，就不寫代碼了

解法二：快慢指針

這道題的快慢指針就與之前的快慢指針思路略有不同，因為求的是倒數第k個，那么我的快慢指針之間可以先隔k個結點，接著快慢指針一起移動，直到快指針指向空為止，此時慢指針的位置就是倒數第k個結點，因為快指針指向空了，快慢指針之間剛好隔了k個結點，所以return慢指針的位置即可

代碼如下：

class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode *fast, *slow;fast = slow = head;while(k--) fast = fast->next;//快指針先走k步while(fast){slow = slow->next;fast = fast->next;}return slow->val;}
};

題目四：合并兩個有序鏈表

將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。?

示例 1：

輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]

示例 2：

輸入：l1 = [], l2 = []
輸出：[]

示例 3：

輸入：l1 = [], l2 = [0]
輸出：[0]

解法：取兩個鏈表中較小的尾插到新鏈表中

對于新鏈表，既可以給哨兵位頭結點，也可以不給，如果有哨兵位的頭結點可以不用判斷是否是第一次尾插，也不會有一些空指針的問題，比較簡單，所以下面就以帶哨兵位頭結點為例：

所以先創建哨兵位的頭結點，賦值給newhead和tail

再進行while循環，判斷條件是(list1 && list2)，表示有一個鏈表為空就停止循環

接著判斷哪一個鏈表還有結點，就將tail->next指向該鏈表，到此成功將list1和list2的結點，按照從小到大的順序尾插到新鏈表中，最后還需將創建的哨兵位頭結點delete掉即可

代碼如下：

class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* newhead, *tail;newhead = tail = new ListNode;//哨兵位頭結點while(list1 && list2)//尾插小的那一個結點{if(list1->val <= list2->val){tail->next = list1;tail = tail->next;list1 = list1->next;}else{tail->next = list2;tail = tail->next;list2 = list2->next;}}//將還有剩余元素的鏈表尾插到新鏈表后面if(list1) tail->next = list1;if(list2) tail->next = list2;ListNode* head = newhead->next;delete newhead; //釋放哨兵位頭結點return head;}
};

題目五：移除鏈表元素

給你一個鏈表的頭節點?head?和一個整數?val?，請你刪除鏈表中所有滿足?Node.val == val?的節點，并返回?新的頭節點?。

示例 1：

輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]

示例 2：

輸入：head = [], val = 1
輸出：[]

示例 3：

輸入：head = [7,7,7,7], val = 7
輸出：[]

解法一：正常遍歷

這道題是一道鏈表的基礎題，只需要定義兩個變量，一個cur，一個prev，其中cur指向head，prev剛開始指向nullptr，即初始是這樣的：

當cur指向的結點不等于val時，prev = cur，cur = cur ->next 即可：

此時cur == val，就讓prev -> next = cur -> next，cur = prev -> next 即可：

到這里尋常的情況就結束了，還需要考慮特殊的情況，例如第一個結點就是需要刪除的結點，此時就不能執行上述邏輯了，因為此時執行prev -> next = cur -> next 這條語句的話，就會造成空指針的問題，所以這里需要特殊處理，剛開始是這樣的：

發現需要頭刪，那就將head = head -> next，cur = head ，這樣就不會造成空指針的問題：

接著進行判斷，發現cur指向的結點不等于val，就執行上述正常的操作：

直到循環結束為止

代碼如下：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* cur = head;ListNode* prev = nullptr;while(cur){if(cur->val == val) // 刪除{//頭刪的情況if(cur == head){head = head->next;cur = head;}//正常的情況else{prev->next = cur->next;cur = prev->next;}}else //正常向后移動{prev = cur;cur = cur->next;}}return head;}
};

解法二：遍歷過程中尾插到新鏈表

在遍歷過程中，如果遇到不等于val的結點，就尾插到新鏈表中，如果等于val就跳過該結點

假設最開始題目所給的條件是這樣：

判斷cur不等于val，又因為是第一次尾插，所以這一次需要將 cur 賦值給 tail 和 head
再將cur = cur->next 即可：

如果繼續cur不等于val，就繼續尾插，此時不是第一次尾插就不需要處理 head 了
只需要將 tail -> next = cur，tail = tail -> next，cur = cur -> next就行：

此時cur指向的結點的val等于val，此時該結點不需要尾插，所以直接 cur = cur -> next：

以此類推....

下面會有幾個特殊情況可能會出錯：

情況一：

當執行結束后，如果原鏈表的最后一個結點的 val 等于 val 時，這時 cur = cur->next 后，循環就結束了，而此時我新鏈表的最后一個結點還是指向的原鏈表的最后一個結點
所以最后需要將tail->next做以處理，將它指向 nullptr 即可

情況二：

而我們如果在代碼的最后執行了上述所說的 tail->next = nullptr 操作，有一種特殊情況，如果原鏈表本身就為空，所以就進不去while循環，此時直接執行這條語句，就會造成空指針的問題，所以還需要針對這種情況做以處理：
在執行 tail->next = nullptr 操作前，先判斷head是否等于空

情況三：

如果原鏈表全部結點的val值都等于val，所以沒有一個結點需要尾插到新鏈表中，此時return的head卻是第一個結點，所以此時的head也不為空，卻也執行了 tail->next = nullptr 語句，依舊出現空指針錯誤，所以在剛開始，將cur = head后，將head置為nullptr即可

代碼如下：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* cur = head;head = nullptr;//防止所有結點的val都等于val的情況ListNode* tail = nullptr;while(cur){ if(cur->val == val) // 跳過該結點{cur = cur->next;}else {//尾插if(tail == nullptr)//判斷是否是第一次尾插{head = tail = cur;cur = cur->next;}else //正常尾插{tail->next = cur;tail = tail->next;cur = cur->next;}}}//處理原鏈表最后一個結點的val值為val時，新鏈表tail->next不為nullptr//和原鏈表本身就是空的情況if(head) tail->next = nullptr;return head;}
};

解法二的新鏈表變為帶有哨兵位的頭結點

在最開始，執行完?cur = head 操作后，將tail和head都指向一個new的結點，不需要處理這個結點的值，因為該結點只是哨兵位的頭結點，再將 tail->next = nullptr

此時就不需要考慮是否最后可以執行 tail->next = nullptr 操作，因為如果原鏈表為空，tail是哨兵位的頭結點，并不是空指針，所以就可以不需要加 if(head) 這句判斷，因此這里可以將上面的情況三也不用考慮了

也不需要處理尾插時是否是第一次尾插的情況，因為已經有哨兵位的頭結點賦值給head和tail了，就不需要考慮第一次尾插時將 cur 賦值給 head 和 tail 的問題了

唯一需要注意的一點是，在創建哨兵位的頭結點時，因為new了一個結點，所以最后return之前需要delete掉，不然就會內存泄漏，雖然不delete，依舊能過測試用例，但是還是能保持良好的做題習慣最好

代碼如下：

class Solution {
public:ListNode* removeElements(ListNode* head, int val) {ListNode* cur = head;ListNode* tail = nullptr;tail = head = new ListNode;//創建哨兵位頭結點tail->next = nullptr; //新鏈表哨兵位頭結點指向nullptrwhile(cur){ if(cur->val == val) // 跳過該結點{cur = cur->next;}else //尾插{tail->next = cur;tail = tail->next;cur = cur->next;}}//處理原鏈表最后一個結點的val值為val時，新鏈表tail->next不為nullptr的情況tail->next = nullptr;//創建哨兵位頭結點new的結點需要delete掉ListNode* del = head;head = head->next;delete del;return head;}
};

題目六：鏈表分割

給你一個鏈表的頭節點?head?和一個特定值?x?，請你對鏈表進行分隔，使得所有?小于?x?的節點都出現在?大于或等于?x?的節點之前。

需要?保留?每個分區中各節點的初始相對位置。

示例 1：

輸入：head = [1,4,3,2,5,2], x = 3
輸出：[1,2,2,4,3,5]

示例 2：

輸入：head = [2,1], x = 2
輸出：[1,2]

注意題目要求了不能改變原來的數據順序，所以頭插相關的思路就可以舍棄掉了，因為頭插會改變順序，所以想到尾插的思路：

創建兩個新鏈表的頭結點，小于x的尾插到 lesshead 后面，大于x的尾插到 greaterhead 后面，最后再將小于x的最后一個結點的next指向greaterhead的第一個結點

需要注意的點是，如果原鏈表的最后一個結點是小于x的，那么greatertail指向的就是原鏈表的中間位置的結點，此時greatertail的next不為空，會指向原鏈表的某一個結點，這時return鏈表時會出問題，所以在最后需要將greatertail的next置空

代碼如下：

class Solution {
public:ListNode* partition(ListNode* pHead, int x) {ListNode *lesshead, *lesstail, *greaterhead, *greatertail;lesshead = lesstail= new ListNode;greaterhead = greatertail = new ListNode;ListNode* cur = pHead;while(cur){if(cur->val < x){//尾插到lesshead鏈表中lesstail->next = cur;lesstail = cur;cur = cur->next;}else{//尾插到greaterhead鏈表中greatertail->next = cur;greatertail = cur;cur = cur->next;}}//lesshead鏈表的尾結點指向greaterhead的頭結點lesstail->next = greaterhead->next;//greatertail的next置空greatertail->next = nullptr;//delete掉new的結點ListNode* delless = lesshead;ListNode* delgreater = greaterhead;ListNode* head = lesshead->next;return head;}
};

題目七：鏈表的回文結構

給定一個鏈表的?頭節點?head?，請判斷其是否為回文鏈表。

如果一個鏈表是回文，那么鏈表節點序列從前往后看和從后往前看是相同的。

示例 1：

輸入: head = [1,2,3,3,2,1]
輸出: true

示例 2：

輸入: head = [1,2]
輸出: false

這道回文結構的鏈表題，有時會要求時間復雜度為O(1)，所以創建一個數組，將鏈表的val放進去，再使用左右雙指針進行判斷這種思路就pass了，正確的思路應該是：

先使用前面所學的知識找到鏈表的中間結點，再將中間結點及之后的結點逆置，然后將鏈表的頭結點與中間結點開始一一比較，最終判斷出是否是回文結構

如上所示，如果是回文結構，從head和mid開始，一一比較，在mid為空之前，他們的結點的val都是一樣的

為了思路更清晰，我們在寫此題時，可以將求中間結點和鏈表的逆置這兩個方法寫成兩個函數，放在同一個類中，在本題所給的函數中調用

代碼如下：

class Solution 
{
public://求鏈表的中間結點ListNode* middleNode(ListNode* head){//雙指針法，一快一慢ListNode* slow, *fast;slow = fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}return slow;}//鏈表的逆置，頭插所有結點ListNode* reverseList(ListNode* head){ListNode* cur = head;ListNode* newhead = new ListNode;newhead->next = nullptr;while(cur){ListNode* next = cur->next;cur->next = newhead->next;newhead->next = cur;cur = next;}ListNode* del = newhead;ListNode* nowhead = newhead->next;delete del;return nowhead;}bool isPalindrome(ListNode* head) {ListNode* mid = middleNode(head);//求中間結點mid = reverseList(mid); //鏈表逆置ListNode* cur = head;while(cur && mid)   //mid與cur，有一個遇空就停止{if(cur->val != mid->val) return false;cur = cur->next;mid = mid->next;}return true;}
};

題目八：相交鏈表

給你兩個單鏈表的頭節點?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回?null?。

圖示兩個鏈表在節點?c1?開始相交：

題目數據?保證?整個鏈式結構中不存在環。

注意，函數返回結果后，鏈表必須?保持其原始結構?

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節點的值為 8 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
— 請注意相交節點的值不為 1，因為在鏈表 A 和鏈表 B 之中值為 1 的節點 (A 中第二個節點和 B 中第三個節點) 是不同的節點。換句話說，它們在內存中指向兩個不同的位置，而鏈表 A 和鏈表 B 中值為 8 的節點 (A 中第三個節點，B 中第四個節點) 在內存中指向相同的位置。

示例?2：

輸入：intersectVal?= 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節點的值為 2 （注意，如果兩個鏈表相交則不能為 0）。
從各自的表頭開始算起，鏈表 A 為 [1,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。

示例?3：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個鏈表不相交，因此返回 null 。

首先最先想到的暴力解法就是，listA的所有結點都與listB的所有結點比較一遍，看地址是否相同，這種實現方式比較簡單，且時間復雜度為O(N^2)，這里就不列舉了

下面說一種時間復雜度為O(N)的思路就能解決：

分別求兩個鏈表的長度，讓長的先走差距步數，此時再同時走，每次觀察地址是否相同就能夠解決問題，因為此時兩個鏈表的長度相同，在分別向后遍歷時，若相交則必定會出現相同地址

此處可以優化的一點是，如果兩個鏈表相交，那么他們的最后一個結點必定相同，所以我們在求長度時，可以求出兩個鏈表的尾結點，求出來后可以進行比較，如果尾結點不同，那就不用做下面的操作了，因為尾結點不同的話兩個鏈表必定不會相交

代碼如下：

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *curA = headA;ListNode *curB = headB;int numA = 0, numB = 0;while(curA->next)//求A的尾結點并求A的長度{curA = curA->next;numA++;}while(curB->next)//求B的尾結點并求B的長度{curB = curB->next;numB++;}if(curA != curB) return nullptr;//先隨機指定長鏈表和短鏈表ListNode* shortList = headA, *longList = headB;if(numA > numB)//如果進入if語句，說明指定錯誤，進行修正{shortList = headB;longList = headA;}int gap = abs(numA - numB);while(gap--) longList = longList->next;//長的走差距步while(shortList != longList){shortList = shortList->next;longList = longList->next;}//走到這里，說明一定相遇了，返回相遇結點return shortList;}
};

題目九：環形鏈表I

給你一個鏈表的頭節點?head?，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數進行傳遞?。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環?，則返回?true?。否則，返回?false?。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例?2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。

關于環形鏈表，也就是尾結點的next不指向空，繼續指向鏈表中的結點，從而遍歷時造成循環的效果，這就稱之為環形鏈表，而普通鏈表就是尾結點的next指向空的鏈表

解法一：遍歷每個結點都與之前的所有結點比較

最容易想到的思路就是：遍歷到每個結點時，都記錄下該結點，下次判斷是否出現重復的結點，這種方式的空間復雜度比較高，效率比較低，這里就不實現了

解法二：使用map每次記錄結點，判斷是否出現過

使用map的思路，結合上述的想法，每次遍歷到新結點時判斷是否出現，map就不會像上面的那種方式，每次都需要從頭到尾比較一遍，map比較的效率是非常高的

class Solution {
public:bool hasCycle(ListNode *head) {unordered_map<ListNode*, int> mp;ListNode* cur = head;while(cur){if(!mp.count(cur)) mp[cur]++;else return true;cur = cur->next;}return false;}
};

解法三：快慢指針

下面是第三種思路，借助前面用過的方法：快慢指針

定義兩個指針，fast、slow表示快慢指針，快指針一次走兩步，慢指針一次走一步，如果鏈表有環，那么快慢指針是一定會在環中相遇的，如果沒環，快指針會走到空

代碼如下：

class Solution {
public:bool hasCycle(ListNode *head) {ListNode *fast = head, *slow = head;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(fast == slow) return true;}return false;}
};

到這里已經解決了這道問題，那么怎么證明在環中fast一定會追到slow呢，其實很簡單，fast每次走兩步，而slow每次走一步，每走一步兩者的距離會縮小一步，那么肯定一步一步就追上了

但是如果fast一次走3步.....n步，slow每次走1步，那么這時就不一定會追上了，如果fast是3步，所以此時每走一步距離縮短兩步，如果兩者相隔的距離是偶數可以追上，如果相隔的距離是奇數，那每次都快2步，最后始終會隔1步，就會有一種可能始終遇不到?

題目十：環形鏈表II

給定一個鏈表的頭節點 ?head?，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。

如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環。注意：pos?不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改?鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例?2：

輸入：head = [1,2], pos = 0
輸出：返回索引為 0 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：返回 null
解釋：鏈表中沒有環。

這道題和上一道題一樣，只不過這道題求的是如果相遇，return相遇的結點

解法一：數學思維

假設一個鏈表從head開始到相遇結點的長度為L，這個鏈表的環長度為C，快指針進入環已經走了N圈，最終與慢指針在meet位置相遇，相遇結點到meet的長度為x，如下圖所示：

slow指針總共走了：L + X長度
fast指針總共走了：L + N*C + X長度

那么既然快指針是滿指針的兩倍速度，所以走的路程也就是兩倍了，就得到下面這個公式：

2*(L + X) = L + N*C?+ X
L + X = N*C?
L = N*C - X
L = (N-1)*C + (C - X)

上面得到的公式表示，L的長度，與從環中meet位置開始走N-1圈后，再走C-X長度相同

所以對照上面的圖，得到一個結論：
一個指針從head位置走，另一個指針從meet位置走，會在環的第一個結點相遇

所以這里的思路就是先使用上一題的方法，找到上一題 return true 的位置，也就是就是meet的位置，再進行實現

將上述的思路轉換為代碼，如下所示：

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//找到meet結點if(fast == slow){//開始兩個指針，分別從head和meet位置走ListNode *meet = fast;while(meet != head){meet = meet->next;head = head->next;}//走到這說明已經走了C-X距離后相遇了return meet;}}return nullptr;}
};

解法二：將環形鏈表轉換為鏈表相交問題

就按上面的這個圖來說：

我們將meet結點指向空，再將meet結點的下一個結點定為newhead，此時將newhead展開：

此題就轉變為了鏈表相交問題，繼續使用前面的快慢指針做即可

可以在轉化后，調用之前寫過的相交鏈表的函數即可：

class Solution {
public://相交鏈表的解題代碼ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode *curA = headA;ListNode *curB = headB;int numA = 0, numB = 0;while(curA->next)//求A的尾結點并求A的長度{curA = curA->next;numA++;}while(curB->next)//求B的尾結點并求B的長度{curB = curB->next;numB++;}if(curA != curB) return nullptr;//先隨機指定長鏈表和短鏈表ListNode* shortList = headA, *longList = headB;if(numA > numB)//如果進入if語句，說明指定錯誤，進行修正{shortList = headB;longList = headA;}int gap = abs(numA - numB);while(gap--) longList = longList->next;//長的走差距步while(shortList != longList){shortList = shortList->next;longList = longList->next;}//走到這里，說明一定相遇了，返回相遇結點return shortList;}ListNode *detectCycle(ListNode *head) {ListNode *fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//找到meet結點if(fast == slow){ListNode *newhead = fast->next;fast->next = nullptr;//調用之前寫的鏈表相交的函數return getIntersectionNode(head,newhead);}}return nullptr;}
};

題目十一：隨機鏈表的復制

給你一個長度為?n?的鏈表，每個節點包含一個額外增加的隨機指針?random?，該指針可以指向鏈表中的任何節點或空節點。

構造這個鏈表的?深拷貝。?深拷貝應該正好由?n?個?全新?節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的?next?指針和?random?指針也都應指向復制鏈表中的新節點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態。復制鏈表中的指針都不應指向原鏈表中的節點?。

例如，如果原鏈表中有?X?和?Y?兩個節點，其中?X.random --> Y?。那么在復制鏈表中對應的兩個節點?x?和?y?，同樣有?x.random --> y?。

返回復制鏈表的頭節點。

用一個由?n?個節點組成的鏈表來表示輸入/輸出中的鏈表。每個節點用一個?[val, random_index]?表示：

val：一個表示?Node.val?的整數。
random_index：隨機指針指向的節點索引（范圍從?0?到?n-1）；如果不指向任何節點，則為??null?。

你的代碼?只?接受原鏈表的頭節點?head?作為傳入參數。

示例 1：

輸入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
輸出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2：

輸入：head = [[1,1],[2,1]]
輸出：[[1,1],[2,1]]

示例 3：

輸入：head = [[3,null],[3,0],[3,null]]
輸出：[[3,null],[3,0],[3,null]]

這道題的題意就是：構造一個新鏈表，使得這個新鏈表和原鏈表中每一個結點的兩個指針都指向的一樣，類似于進行一個深拷貝

解法一：不借助容器

而這里所給的鏈表，每個結點都有兩個指針，其中一個就是普通的next指針，還有一個是random指針，表示隨機指向鏈表中的某個位置，這道題的難點就是這個random指針，怎么深拷貝出來

因為next指針可以遍歷時一步一步拷貝，而random指針所指向的結點，原鏈表和新深拷貝出來的鏈表地址是不同的，所以就需要仔細思考如何處理這個問題

可能有一種想法是原鏈表指向的結點的val時多少，我就在新鏈表中找這個 val值的結點，但是這種思路可能會出現多個 val值相同的結點，會有問題，就算鏈表的 val值不重復，效率也是非常低的，每個結點都需要遍歷一遍鏈表，時間復雜度為O(N^2)了

所以下面講講正確的思路：

第一步、將copy的每個結點都鏈接到源結點的后面
變為：

第二步、開始遍歷原鏈表，copy->random = cur->random->next

如果原鏈表cur->random指向nullptr，那copy->random也指向nullptr

如果原鏈表cur->random不指向空，那么執行copy->random = cur->random->next

因為原鏈表cur結點的random指向的是第一個結點，所以copy->random就指向原結點的random的下一個結點，也就是深拷貝出的這個結點，就能夠完美的找到拷貝結點的random指向的結點，只要能夠找到原結點的random指向，那么copy結點的random指向就是原結點的next結點

能夠進行上述操作的前提就是，我們第一步做的將copy結點鏈接到了原結點的后面，這樣就能夠找到copy結點的random指向的結點了

第三步、拷貝節點解下來，鏈接到一起，恢復原鏈表

從而得到了隨機鏈表的復制，代碼如下：

class Solution 
{
public:Node* copyRandomList(Node* head) {// 1.拷貝鏈表到原鏈表的后面Node* cur = head;while(cur){Node* next = cur->next;Node* copy = new Node(cur->val);cur->next = copy;//改變cur->next指向copy->next = next;//改變copy->next指向cur = next;}// 2.遍歷鏈表，實現copy結點的random指針的指向cur = head;while(cur){Node* copy = cur->next;if(cur->random)//cur->random不指向空copy->random = cur->random->next;else //cur->random指向空copy->random = nullptr;cur = copy->next;}// 3.將拷貝結點解下來cur = head;Node* newhead = new Node(0);newhead->next = nullptr;Node* tail = newhead;while(cur){Node* copy = cur->next;cur->next = copy->next;cur = cur->next;//cur繼續往后走tail->next = copy;tail = copy;}return newhead->next;}
};

解法二：使用哈希表進行映射

使用map，將源節點與拷貝節點進行映射，也是能夠實現的

代碼如下：

class Solution 
{
public:Node* copyRandomList(Node* head) {if(head == nullptr) return nullptr;unordered_map<Node*, Node*> mp;Node* cur = head;while(cur){Node* copy = new Node(cur->val);mp[cur] = copy;//原鏈表與拷貝鏈表結點一一對應cur = cur->next;}cur = head;while(cur){//依靠哈希表進行random和next的指向mp[cur]->random = mp[cur->random];mp[cur]->next = mp[cur->next];cur = cur->next;}return mp[head];}
};

題目十二：兩數相加

給你兩個?非空?的鏈表，表示兩個非負的整數。它們每位數字都是按照?逆序?的方式存儲的，并且每個節點只能存儲?一位?數字。

請你將兩個數相加，并以相同形式返回一個表示和的鏈表。

你可以假設除了數字 0 之外，這兩個數都不會以 0?開頭。

示例 1：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

示例 2：

輸入：l1 = [0], l2 = [0]
輸出：[0]

示例 3：

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

提示：

每個鏈表中的節點數在范圍?[1, 100]?內
0 <= Node.val <= 9
題目數據保證列表表示的數字不含前導零

首先題目明確說明了，鏈表所表示的數字是按照逆序的方式存儲的，也就是原本是128，那么鏈表中存儲的就是821，這樣是為了方便我們計算的，因為我們在做加法時，就是從后往前開始加的，這里鏈表逆序的話，我們直接從頭往后加即可

在這道題的while判斷條件中，條件不是 &&，而是 ||，因為加法運算，一個數沒有了就不計算這個了，把它當做0即可

while的條件中還有 || num，因為可能兩個數的最后一位加完，還有進位num，所以這時還需要再new一個結點出來，存儲這個進位

代碼如下：

class Solution {
public:ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {ListNode* cur1 = l1, *cur2 = l2;ListNode* newhead = new ListNode(0);//哨兵位頭結點newhead->next = nullptr;ListNode* tail = newhead;//尾指針int num = 0; //記錄進位while(cur1 || cur2 || num){if(cur1) //cur1不為空{num += cur1->val;cur1 = cur1->next;}if(cur2) //cur2不為空{num += cur2->val;cur2 = cur2->next;}ListNode* node = new ListNode(num % 10);//將個位給nodenum /= 10; //num表示進位，所以除10，保留十位tail->next = node;tail = node;}ListNode* del = newhead;//釋放new出的哨兵位頭結點ListNode* head = newhead->next;delete newhead;return head;}
};

題目十三：兩兩交換鏈表中的結點

給你一個鏈表，兩兩交換其中相鄰的節點，并返回交換后鏈表的頭節點。你必須在不修改節點內部的值的情況下完成本題（即，只能進行節點交換）。

示例 1：

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]

示例 2：

輸入：head = []
輸出：[]

示例 3：

輸入：head = [1]
輸出：[1]

這道題后面在遞歸的題目練習中也會使用做到，這里使用的是循環、迭代的方式

先new一個哨兵位頭結點，就不需要額外的處理一些邊界條件了

為了方便交換，可以多定義幾個變量，cur的前一個結點為prev，遍歷的當前結點為cur，與當前結點進行交換的為next，next的下一個結點為nnext，如下所示：

上圖是交換完以后的指針對應情況，接下來應該變為prev、cur、next、nnext這個順序：

所以就需要循環一次以后改變上述指針的對應位置

下面說明循環的結束條件，如果是偶數的情況，cur走到這一步就該停止循環了：

如果是奇數的情況，cur走到這一步就該停止循環了：

所以結束條件就是，cur&&next為空就停止

代碼如下：

class Solution 
{
public:ListNode* swapPairs(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* newhead = new ListNode;newhead->next = head;//定義四個指針，分別指向包含哨兵位的前四個結點ListNode* prev = newhead, *cur = prev->next, *next = cur->next, *nnext = next->next;while(cur && cur->next){//交換后的各個指針的指向情況prev->next = next;next->next = cur;cur->next = nnext;//改變prev、cur、next和nnext的指向prev = cur;cur = nnext;//如果cur或是next為空，就表示是鏈表個數是奇數個，下一次就停止循環了//此時就不能給next和nnext賦值了，不然就會出現空指針問題if(cur) next = cur->next;if(next) nnext = next->next;}return newhead->next;}
};

題目十四：重排鏈表

給定一個單鏈表?L?的頭節點?head?，單鏈表?L?表示為：

L0 → L1 → … → Ln - 1 → Ln

請將其重新排列后變為：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

示例 1：

輸入：head = [1,2,3,4]
輸出：[1,4,2,3]

示例 2：

輸入：head = [1,2,3,4,5]
輸出：[1,5,2,4,3]

這道題要求將一個給定的鏈表，第一個結點->最后一個結點->第二個結點->倒數第二個結點 ...

按照這種順序排列，例如1->2->3->4變為1->4->2->3

仔細觀察變化后的鏈表，我們可以發現，如果將原鏈表從中間位置切成兩部分，將后半部分逆置，也就是變為了1->2->4->3，此時前半部分是1->2，后半部分是4->3，接著前半部分取一個數，后半部分取一個數，這樣依次取值，就得到了1->4->2->3的結果

所以這道題分為三步：

①找到鏈表的中間結點
②后半部分鏈表逆序
③合并兩個鏈表

可以看到這三步，在前面都是做過類似的題目的，下面分析一下題目的細節

第一步找鏈表的中間結點，是用快慢雙指針的方法找到的中間結點，此時slow指向的就是中間結點

第二步后半部分鏈表逆序，有兩種方式，第一種是從slow開始逆序，第二種是從slow->next開始逆序

第一種方式很好理解，因為從哪里劃分的就從哪里逆序，那么為什么要有第二種呢，很簡單，因為第三步是合并兩個鏈表，需要有兩個單獨的鏈表，前半部分的最后一個結點時需要指向空的

如果是第二種方式，我想斷開前半部分和后半部分，只需要將slow->next = nullptr即可，因為slow可以歸屬到前半部分去，不需要做其他處理，而第一種找到中間結點后無法找到前半部分的最后一個結點，將前半部分置空，下面說說為什么可以這樣做：

如果是奇數個結點，這樣做很好理解，那如果是偶數個，例如原鏈表為1->2->3->4，找到的中間結點是3，那么這種方式就是從結點4開始逆序，重排以后應該是1->4->2->3，觀察最終結果，中間結點和它前面的結點也就是2和3，在重排完之后依舊是連在一起的，所以在這種方式下我們可以將中間結點歸到前半部分去，最終的結果也是正確的

第三步合并兩個鏈表，經過上面的步驟，成功將兩個鏈表斷開了，下面只需要將這兩個斷開的鏈表尾插到新鏈表中即可，循環的判斷條件為第一個鏈表不為空，因為無論是奇數還是偶數都是第一個鏈表的結點數量多，如下所示：

代碼如下：

class Solution {
public:void reorderList(ListNode* head) {//如果沒有結點，或是只有1個或2個結點，直接return，因為順序不變if(head == nullptr || head->next == nullptr || head->next->next == nullptr) return;//找中間結點，快慢雙指針ListNode* fast = head, *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;}//逆序后半部分鏈表ListNode* newhead = new ListNode;//創建哨兵位頭結點ListNode* cur = slow->next; //從slow->next開始逆序slow->next = nullptr; //將前半部分最后一個結點指向空，斷開兩個鏈表while(cur) {ListNode* next = cur->next;cur->next = newhead->next;newhead->next = cur;cur = next;}//合并兩個鏈表ListNode* ret = new ListNode;ListNode* tail = ret;ListNode* cur1 = head, *cur2 = newhead->next;while(cur1){//先尾插第一個鏈表tail->next = cur1;cur1 = cur1->next;tail = tail->next;//再尾插第二個鏈表，可能為空，所以需要先判斷if(cur2){tail->next = cur2;cur2 = cur2->next;tail = tail->next;}}//釋放new的結點delete newhead;delete ret;}
};

題目十五：合并 k 個升序鏈表

給你一個鏈表數組，每個鏈表都已經按升序排列。

請你將所有鏈表合并到一個升序鏈表中，返回合并后的鏈表。

示例 1：

輸入：lists = [[1,4,5],[1,3,4],[2,6]]
輸出：[1,1,2,3,4,4,5,6]
解釋：鏈表數組如下：
[1->4->5,1->3->4,2->6
]
將它們合并到一個有序鏈表中得到。
1->1->2->3->4->4->5->6

示例 2：

輸入：lists = []
輸出：[]

示例 3：

輸入：lists = [[]]
輸出：[]

解法一：暴力解法

暴力解法就是：先合并前兩個有序鏈表為一個新鏈表，再接著兩兩往下合并，由于這種算法的時間復雜度過大，所以代碼就不寫了，看下面的解法

解法二：優先級隊列做優化

這種解法參考了上面做過的合并兩個有序鏈表的題目，由于在合并兩個有序鏈表那里，只有兩個鏈表，所以比較好比較哪個鏈表的當前結點是較小的那一個，而這道題是k個鏈表，采用比較的方式不太好比較誰是較小的結點，所以引入了優先級隊列(小根堆)，將k個鏈表的當前指向的結點都放入優先級隊列中，堆頂結點就是最小的結點，此時拿出堆頂的結點尾插入新鏈表中，再將該結點所在的鏈接向后移動，繼續插入優先級隊列中

這種算法的時間復雜度是O(N* K * logK)，每個鏈表長度為N，有K個鏈表，優先級隊列的時間復雜度為logK

代碼如下：

class Solution {
public://cmp仿函數，判斷每個結點的val值struct cmp{bool operator()(const ListNode* t1, const ListNode* t2){return t1->val > t2->val;//大于就向下調整}};ListNode* mergeKLists(vector<ListNode*>& lists) {//創建一個小根堆priority_queue<ListNode*, vector<ListNode*>, cmp> heap;//讓所有鏈表的頭結點進入小根堆for(auto& iter : lists){if(iter) heap.push(iter);}//創建哨兵位頭結點，合并k個鏈表ListNode* newhead = new ListNode;ListNode* tail = newhead;while(!heap.empty()){ListNode* small = heap.top();heap.pop();tail->next = small;tail = small;small = small->next;//判斷當前結點是否為空if(small) heap.push(small);}//釋放new出來的頭結點ListNode* del = newhead;ListNode* head = newhead->next;delete del;return head;}
};

解法三：分治 - 遞歸

這道題如果使用遞歸分治的思路，時間復雜度依舊是O(N*K*logK)，分析如下：

假設有K個鏈表，那么二叉樹的高度就是logK，鏈表中有N個結點，每個結點都會合并logK次，此時每個鏈表的時間復雜度是O(N*logK)，又因為有K個鏈表，所以時間復雜度是O(N*K*logK)

這道題的遞歸解法，與前面的分治中遞歸的解法，幾乎一模一樣，只不過之前是每次合并兩個數組，這道題是每次合并兩個鏈表?

代碼如下：

class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {if(lists.size() == 0) return nullptr;if(lists.size() == 1) return lists[0];return merge(lists, 0, lists.size()-1);}ListNode* merge(vector<ListNode*>& lists, int left, int right){if(left > right) return nullptr;;if(left == right) return lists[left];;//左右區間排序int mid = ((right - left) >> 1) + left;ListNode* cur1 = merge(lists, left, mid);ListNode* cur2 = merge(lists, mid + 1, right);//合并兩個鏈表ListNode* newhead = new ListNode;ListNode* tail = newhead;while(cur1 && cur2){if(cur1->val < cur2->val){tail->next = cur1;tail = cur1;cur1 = cur1->next;}else{tail->next = cur2;tail = cur2;cur2 = cur2->next;}}//處理兩個鏈表可能有一個還有元素的情況if(cur1) tail->next = cur1;if(cur2) tail->next = cur2;//new的結點delete掉ListNode* del = newhead;ListNode* head = newhead->next;delete del;return head;}
};

題目十六：K 個一組翻轉鏈表

給你鏈表的頭節點?head?，每?k?個節點一組進行翻轉，請你返回修改后的鏈表。

k?是一個正整數，它的值小于或等于鏈表的長度。如果節點總數不是?k?的整數倍，那么請將最后剩余的節點保持原有順序。

你不能只是單純的改變節點內部的值，而是需要實際進行節點交換。

示例 1：

輸入：head = [1,2,3,4,5], k = 2
輸出：[2,1,4,3,5]

示例 2：

輸入：head = [1,2,3,4,5], k = 3
輸出：[3,2,1,4,5]

這道題其實就是模擬，模擬給你的算法過程

首先我們需要知道這個鏈表需要逆序多少組，在知道需要逆序n組后，只需要重復n次逆序過程，并且保證每次逆序完成后，能夠保持鏈表的鏈接關系即可

以示例一舉例：head = [1,2,3,4,5]，k = 2

鏈表中共5個結點，k = 2，所以5 / 2 = 2，算出來需要逆序2組，也就是 [1,2] 和 [3,4]，最后的這個[5]不用動，鏈接到前兩組逆序完以后得后面即可

逆序完 [1,2]，變為 [2,1]，此時逆序 [3,4] 的時候，需要跟在結點1后面，所以為了方便起見，提前記錄結點1，這樣下次逆序時就能很快找到該結點

逆序的過程已經做過非常多的題目了，也就是頭插法

代碼如下：

class Solution {
public:ListNode* reverseKGroup(ListNode* head, int k) {ListNode* cur = head;int num = 0;//計算鏈表中結點的個數while(cur){num++;cur = cur->next;}//num就是需要逆序的數組個數num /= k;//創建哨兵位頭結點，方便頭插ListNode* newhead = new ListNode;ListNode* prev = newhead;prev->next = nullptr;cur = head;      while(num--){int ret = k;ListNode* tmp = cur;//記錄下一次需要頭插的位置while(ret--){ListNode* next = cur->next;cur->next = prev->next;prev->next = cur;cur = next;}prev = tmp;//更新prev，也就是下一次需要頭插的位置prev->next = nullptr;}//把不需要反轉的結點接上prev->next = cur;ListNode* del = newhead;ListNode* ret = newhead->next;delete del;return ret;}
};

鏈表題目到此結束啦