本篇練習題(單鏈表)：

1.力扣 203. 移除鏈表元素

2.力扣 206. 反轉鏈表

3.力扣 876. 鏈表的中間結點

4.力扣 21. 合并兩個有序鏈表

5. 牛客 鏈表分割算法詳解

6.牛客 鏈表回文結構判斷

7. 力扣 160. 相交鏈表

8. 力扣 141 環形鏈表

9. 力扣 142 環形鏈表 II

10. 力扣 138. 隨機鏈表的復制

1.力扣 203. 移除鏈表元素：構建新鏈表解法詳解

一、題目概述

給定一個鏈表的頭節點?head?和一個整數?val，需要刪除鏈表中所有滿足?Node.val == val?的節點，并返回新的頭節點。例如，輸入鏈表?[1,2,6,3,4,5,6]，val=6，輸出?[1,2,3,4,5]。

二、代碼實現

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeElements(struct ListNode* head, int val) {struct ListNode* pcur, *newhead, *newtail;pcur = head;newhead = newtail = NULL;while (pcur) {if (pcur->val != val) {if (newhead == NULL) {newhead = newtail = pcur;} else {newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;}if (newtail) {newtail->next = NULL;}return newhead;
}

三、代碼逐行詳解

1. 初始化指針

struct ListNode* pcur, *newhead, *newtail;
pcur = head;          // 用于遍歷原鏈表
newhead = newtail = NULL;  // 新鏈表頭、尾，初始為空

• pcur：遍歷原鏈表的指針，從頭部?head?開始。
• newhead?和?newtail：構建新鏈表的指針，初始時新鏈表無節點，均為?NULL。

2. 遍歷原鏈表，構建新鏈表

while (pcur) {if (pcur->val != val) {  // 僅處理值不為 val 的節點if (newhead == NULL) {  // 新鏈表為空，初始化頭和尾newhead = newtail = pcur;} else {  // 新鏈表已有節點，連接到尾部newtail->next = pcur;newtail = newtail->next;}}pcur = pcur->next;  // 原鏈表指針后移
}

• 循環邏輯：遍歷原鏈表每個節點。
• 條件判斷：若節點值不等于?val，則加入新鏈表：
  • 新鏈表為空時，當前節點既是頭?newhead?也是尾?newtail。
  • 新鏈表非空時，將當前節點接到?newtail?之后，更新?newtail?到新位置。
• 無論是否處理當前節點，pcur?都會后移，確保遍歷完整原鏈表。

3. 處理新鏈表尾節點

if (newtail) {newtail->next = NULL;  // 斷開與原鏈表的連接，保證新鏈表結構正確
}
return newhead;  // 返回新鏈表頭

• 若新鏈表存在（newtail?非空），將尾節點的?next?置為?NULL，避免殘留原鏈表節點。
• 最后返回新鏈表頭?newhead，即刪除目標節點后的結果。

四、核心思想與復雜度分析

核心思想

通過構建新鏈表的方式，僅保留值不為?val?的節點。這種方法簡化了刪除操作，無需處理原鏈表頭節點刪除的特殊情況，邏輯更清晰。

復雜度分析

• 時間復雜度：(O(N))，僅遍歷原鏈表一次，n?為鏈表節點數。
• 空間復雜度：(O(1))，僅使用常數級額外指針，未創建新數據結構。

五、總結

本文通過構建新鏈表的方法解決了 “移除鏈表元素” 問題。該思路通過遍歷原鏈表，有選擇性地構建新鏈表，避免了復雜的節點刪除操作。理解這種解題方式，有助于加深對鏈表操作的理解，在處理類似鏈表修改問題時提供新思路。

2.力扣 206. 反轉鏈表：迭代法代碼詳解與實現

一、引言

鏈表反轉是鏈表操作中的經典問題。在力扣 206 題中，給定單鏈表的頭節點?head，需要反轉鏈表并返回反轉后的頭節點。本文將詳細講解迭代法實現鏈表反轉的代碼邏輯，幫助大家理解這一經典算法。

---

二、迭代法核心思路

迭代法反轉鏈表的核心是通過三個指針：n1（記錄當前節點的前驅）、n2（當前處理的節點）、n3（暫存當前節點的后繼），在遍歷鏈表時逐步修改節點的?next?指針，使其指向前驅節點，最終完成鏈表反轉。

---

三、代碼逐行詳解

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {// 處理空鏈表情況if (head == NULL) {return head;}ListNode* n1, *n2, *n3;n1 = NULL;       // n1 指向當前節點的前驅，初始無前驅n2 = head;       // n2 指向當前處理的節點（從原鏈表頭開始）n3 = n2->next;   // 暫存當前節點的后繼，防止斷鏈while (n2) {     // 遍歷鏈表，直到處理完所有節點// 反轉指針：當前節點 n2 的 next 指向其前驅 n1n2->next = n1;// 指針后移n1 = n2;     // n1 變為當前節點n2 = n3;     // n2 處理下一個節點if (n3) {    // 若后繼節點存在，n3 后移n3 = n3->next;}}return n1;       // 最終 n1 指向反轉后的頭節點
}

代碼分段解析

1. 空鏈表處理：

   if (head == NULL) {return head;
   }
   

   若輸入鏈表為空，直接返回?head，無需處理。

2. 指針初始化：

   ListNode* n1, *n2, *n3;
   n1 = NULL;
   n2 = head;
   n3 = n2->next;
   

   • n1?記錄當前節點的前驅，初始為?NULL（頭節點無前驅）。
   • n2?指向當前處理的節點（從原鏈表頭開始）。
   • n3?暫存?n2?的后繼節點，避免修改?n2->next?時鏈表斷裂。

3. 迭代反轉：

   while (n2) {n2->next = n1;n1 = n2;n2 = n3;if (n3) {n3 = n3->next;}
   }
   

   • 反轉指針：n2->next = n1?將當前節點的指針指向其前驅，完成局部反轉。
   • 指針后移：
     • n1 = n2：n1?后移，變為當前節點。
     • n2 = n3：n2?后移，處理下一個節點。
     • n3 = n3->next：若?n3?存在，繼續暫存后續節點，確保鏈表遍歷不斷鏈。

4. 返回結果：

   return n1;
   

   循環結束后，n1?指向原鏈表的最后一個節點（即反轉后的頭節點），直接返回。

---

四、算法復雜度分析

• 時間復雜度：(O(N))，需遍歷鏈表一次，處理每個節點。
• 空間復雜度：(O(1))，僅使用常數級別的額外指針變量，未占用額外線性空間。

---

五、總結

迭代法反轉鏈表通過三個指針的配合，在遍歷鏈表過程中完成指針反轉，邏輯清晰且效率高。理解這一方法不僅能解決力扣 206 題，還能為后續復雜鏈表操作（如 K 個一組反轉鏈表）打下基礎。掌握指針操作的核心思想，就能靈活應對各類鏈表問題。

3. 力扣 876. 鏈表的中間結點：快慢指針解法深度解析

引言

在鏈表問題中，“找中間節點” 是一個經典題型。力扣 876 題要求我們找到鏈表的中間節點，若有兩個中間節點，返回第二個。本文將通過快慢指針法高效解決該問題，深入解析代碼邏輯與算法思想。

---

一、題目分析

題目描述：給定單鏈表的頭結點?head，返回鏈表的中間節點。若節點數為偶數，返回第二個中間節點。
示例：

• 輸入?[1,2,3,4,5]，輸出?3（奇數節點，中間一個）。
• 輸入?[1,2,3,4,5,6]，輸出?4（偶數節點，返回第二個中間節點）。

---

二、算法思路：快慢指針法

核心思想

定義兩個指針：

• 慢指針?slow：每次移動 1 步。
• 快指針?fast：每次移動 2 步。
  當快指針無法繼續移動（即?fast?或?fast->next?為空）時，慢指針恰好指向中間節點。

數學邏輯

• 鏈表長度為奇數：快指針走完鏈表時，慢指針正好在正中間。
• 鏈表長度為偶數：快指針超出鏈表范圍時，慢指針落在第二個中間節點。

---

三、代碼詳細解析

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;struct ListNode* middleNode(struct ListNode* head) {ListNode* slow = head; // 慢指針初始化，指向頭節點ListNode* fast = head; // 快指針初始化，指向頭節點// 循環條件：快指針能繼續移動兩步while (fast && fast->next) {slow = slow->next;    // 慢指針每次走 1 步fast = fast->next->next; // 快指針每次走 2 步}return slow; // 循環結束，slow 指向中間節點
}

代碼逐行解釋：

1. typedef struct ListNode ListNode;：簡化結構體名稱，方便后續代碼書寫。
2. 初始化?slow?和?fast?均指向頭節點?head。
3. while (fast && fast->next)：確保快指針能移動兩步，避免越界。
4. 循環內，slow?走 1 步，fast?走 2 步。
5. 循環結束后，slow?指向目標中間節點，直接返回。

---

四、示例演示

示例 1：輸入?[1,2,3,4,5]

• 初始：slow?和?fast?指向?1。
• 第一次循環：slow?到?2，fast?到?3。
• 第二次循環：slow?到?3，fast?到?5。
• 第三次檢查：fast->next?為空，退出循環，返回?slow（值為?3）。

示例 2：輸入?[1,2,3,4,5,6]

• 初始：slow?和?fast?指向?1。
• 第一次循環：slow?到?2，fast?到?3。
• 第二次循環：slow?到?3，fast?到?5。
• 第三次循環：slow?到?4，fast?嘗試移動到?7（越界，退出循環）。
• 返回?slow（值為?4）。

---

五、算法復雜度分析

• 時間復雜度：O (N)。快慢指針遍歷鏈表一次，僅需一次線性掃描。
• 空間復雜度：O (1)。僅使用常數級額外空間（兩個指針）。

---

總結

快慢指針法是解決鏈表中間節點問題的經典方案，通過控制指針移動速度的差異，高效定位目標節點。該方法不僅適用于本題，還廣泛應用于鏈表環檢測、倒數第 k 個節點等問題。掌握這一思想，能大幅提升鏈表類題目的解題效率。

4. 力扣 21. 合并兩個有序鏈表：代碼詳解與思路分析

一、引言

在鏈表操作中，“合并兩個有序鏈表” 是一道經典題目。它不僅考察對鏈表結構的理解，還考驗邏輯處理能力。本文將以 LeetCode 21 題為例，詳細講解解題思路，并對代碼逐行分析，幫助大家徹底掌握這一問題。

二、題目分析

題目要求：將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表通過拼接給定的兩個鏈表的所有節點組成。 例如： 輸入：l1 = [1,2,4],?l2 = [1,3,4] 輸出：[1,1,2,3,4,4]

三、解題思路

1. 虛擬頭節點的妙用

創建一個虛擬頭節點?nodehead，它作為新鏈表的 “臨時起點”。這樣做的好處是：避免處理空鏈表時的復雜邊界條件，讓代碼邏輯更統一。

2. 遍歷比較節點

同時遍歷兩個鏈表，比較當前節點值：

• 若?l1?當前節點值更小，將其接入新鏈表；
• 若?l2?當前節點值更小，將其接入新鏈表。 通過一個尾指針?nodetail?始終跟蹤新鏈表的末尾，方便追加節點。

3. 處理剩余節點

遍歷結束后，若其中一個鏈表還有剩余節點（因鏈表長度可能不同），直接將剩余部分接到新鏈表末尾（輸入鏈表本身有序，無需再比較）。

四、代碼逐行詳解

#include <stdlib.h>// 鏈表節點定義
typedef struct ListNode {int val;struct ListNode *next;
} ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {// 處理特殊情況：若其中一個鏈表為空，直接返回另一個if (list1 == NULL) {return list2;}if (list2 == NULL) {return list1;}// 創建虛擬頭節點和尾指針ListNode* nodehead = (ListNode*)malloc(sizeof(ListNode));ListNode* nodetail = nodehead;nodehead->next = NULL;ListNode* l1 = list1;ListNode* l2 = list2;// 遍歷合并while (l1 && l2) {if (l1->val > l2->val) {// l2 當前節點更小，接入新鏈表nodetail->next = l2;nodetail = nodetail->next;l2 = l2->next;} else {// l1 當前節點更小，接入新鏈表nodetail->next = l1;nodetail = nodetail->next;l1 = l1->next;}}// 處理剩余節點if (l1) {nodetail->next = l1;}if (l2) {nodetail->next = l2;}// 提取真實頭節點，釋放虛擬頭節點ListNode* result = nodehead->next;free(nodehead);nodehead = NULL;return result;
}

代碼解釋：

1. 特殊情況處理： 直接判斷?list1?或?list2?為空的情況，返回另一個鏈表。

2. 虛擬頭節點初始化： nodehead?作為虛擬頭，nodetail?始終指向新鏈表末尾，初始時都指向?nodehead。

3. 遍歷合并： while?循環中，比較?l1?和?l2?當前節點值，將較小節點接入新鏈表，尾指針?nodetail?后移。

4. 處理剩余節點： 循環結束后，若?l1?或?l2?有剩余，直接接到?nodetail?后。

5. 釋放內存與返回： 提取真實頭節點?result，釋放虛擬頭節點?nodehead，避免內存泄漏。

五、完整代碼測試

// 測試代碼（可補充完整測試邏輯）
int main() {// 構建測試用例鏈表（此處省略具體構建過程）return 0;
}

六、總結

• 時間復雜度：\(O(m + n)\)，其中?m?和?n?分別為兩個鏈表的長度，需遍歷每個節點一次。
• 空間復雜度：\(O(1)\)，除虛擬頭節點外，未使用額外與輸入規模相關的空間。 通過虛擬頭節點簡化操作，結合遍歷比較和剩余節點處理，我們高效解決了合并有序鏈表問題。這一思路在鏈表操作中非常通用，值得深入理解和記憶。

5. 牛客 鏈表分割算法詳解： 風格實現與解析

一、問題描述

給定一個鏈表的頭指針?ListNode* pHead?和一個整數值?x，需將所有小于?x?的節點排在其余節點之前，同時保持原有數據順序，最后返回重排后的鏈表頭指針。

二、代碼實現

struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(NULL) {}
};class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// 初始化兩個啞節點（哨兵節點）ListNode* lessHead = new ListNode(-1);  // 存儲小于x的節點ListNode* lessTail = lessHead;ListNode* greaterHead = new ListNode(-1);  // 存儲大于等于x的節點ListNode* greaterTail = greaterHead;ListNode* pCur = pHead;while (pCur) {if (pCur->val < x) {// 連接到less鏈表lessTail->next = pCur;lessTail = lessTail->next;} else {// 連接到greater鏈表greaterTail->next = pCur;greaterTail = greaterTail->next;}pCur = pCur->next;}// 處理greater鏈表的末尾，避免循環引用greaterTail->next = NULL;// 合并less和greater鏈表lessTail->next = greaterHead->next;// 釋放啞節點內存ListNode* ret = lessHead->next;delete lessHead;delete greaterHead;return ret;}
};

三、代碼詳細解析

1. 鏈表節點定義

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

定義鏈表節點結構，val?存儲節點值，next?指向下一節點，構造函數初始化節點值并默認?next?為?NULL。

2. 初始化啞節點

ListNode* lessHead = new ListNode(-1);  
ListNode* lessTail = lessHead;
ListNode* greaterHead = new ListNode(-1);  
ListNode* greaterTail = greaterHead;

創建兩個啞節點?lessHead?和?greaterHead，作為臨時鏈表的頭。lessTail?和?greaterTail?跟蹤各自鏈表的尾部，便于后續節點追加。

3. 遍歷原鏈表并分割

ListNode* pCur = pHead;
while (pCur) {if (pCur->val < x) {lessTail->next = pCur;lessTail = lessTail->next;} else {greaterTail->next = pCur;greaterTail = greaterTail->next;}pCur = pCur->next;
}

遍歷原鏈表：

• 若節點值小于?x，追加到?less?鏈表（lessTail?后）；
• 否則，追加到?greater?鏈表（greaterTail?后）；
• 移動?pCur?繼續遍歷。

4. 合并鏈表與內存釋放

greaterTail->next = NULL;  // 斷開greater鏈表尾
lessTail->next = greaterHead->next;  // 合并less和greaterListNode* ret = lessHead->next;
delete lessHead;
delete greaterHead;
return ret;

• 處理?greater?鏈表尾，避免懸空引用；
• 合并?less?與?greater?鏈表；
• 釋放啞節點內存，返回合并后鏈表的頭節點。

四、算法分析

• 時間復雜度：O (n)，僅一次遍歷鏈表。
• 空間復雜度：O (1)，使用常數級額外空間（啞節點）。
• 穩定性：保持節點相對順序，因按遍歷順序分配到兩個鏈表。

五、總結

通過啞節點簡化鏈表操作，將原鏈表拆分為兩個子鏈表后合并，高效實現鏈表分割。此方法邏輯清晰，內存管理規范，是鏈表操作的經典思路。掌握啞節點的使用，能更便捷地處理鏈表頭節點相關問題。

6.牛客 鏈表回文結構判斷：經典解法詳解與實現

引言

在鏈表算法問題中，判斷鏈表是否為回文結構是一道經典題目。回文結構意味著鏈表正讀和反讀的節點值序列一致，如?1->2->2->1。本文將介紹一種高效解法：利用快慢指針找中間節點，反轉后半部分鏈表，最后對比前后部分，實現時間復雜度 O (n)、空間復雜度 O (1) 的最優解。

---

一、解題思路分析

1. 找中間節點（快慢指針法）

• 原理：快指針每次走兩步，慢指針每次走一步。當快指針到達鏈表末尾時，慢指針恰好位于中間位置。若鏈表長度為偶數，慢指針指向后半部分第一個節點。
• 作用：將鏈表拆分為前后兩部分，為后續反轉后半部分做準備。

2. 反轉后半部分鏈表

• 原理：通過迭代法，調整節點的?next?指針方向，實現鏈表反轉。
• 作用：反轉后，后半部分鏈表的節點順序與前半部分對稱，便于直接對比。

3. 前后對比驗證

• 原理：同時遍歷原前半部分鏈表和反轉后的后半部分鏈表，逐節點比較值是否相等。
• 作用：若所有對應節點值一致，鏈表為回文結構；否則不是。

---

二、代碼實現與逐函數解析

1. 定義鏈表節點結構

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

2.?middleNode：找中間節點

ListNode* middleNode(ListNode* head) {  ListNode* slow, *fast;  slow = fast = head;  while (fast && fast->next) {  slow = slow->next;       // 慢指針一步  fast = fast->next->next; // 快指針兩步  }  return slow; // 返回中間節點  
}  

• 邏輯：快慢指針從頭部出發，快指針移動到末尾時，慢指針指向中間。例如，鏈表?1->2->3->4，最終?slow?指向?3。

3.?reverseList：反轉鏈表

ListNode* reverseList(ListNode* head) {  if (head == NULL) return head;  ListNode* n1 = NULL, *n2 = head, *n3 = head->next;  while (n2) {  n2->next = n1;   // 反轉指針方向  n1 = n2;         // 指針后移  n2 = n3;  if (n3) n3 = n3->next; // 避免空指針  }  return n1; // 反轉后新頭節點  
}  

• 邏輯：通過?n1（前驅）、n2（當前）、n3（后繼）三個指針，逐步調整節點指向。例如，輸入?2->1，反轉后返回?1->2。

4.?chkPalindrome：判斷回文

bool chkPalindrome(ListNode* A) {  ListNode* mid = middleNode(A);       // 找中間節點  ListNode* right = reverseList(mid);  // 反轉后半部分  ListNode* left = A;                  // 前半部分起點  while (right) {  if (left->val != right->val) return false; // 對比失敗，非回文  left = left->next;  right = right->next;  }  return true; // 全部匹配，是回文  
}  

• 邏輯：先拆分、反轉鏈表，再同時遍歷前后兩部分。若節點值不一致，直接返回?false；遍歷結束無沖突，返回?true。

---

三、代碼優勢與復雜度分析

• 時間復雜度：O (n)。找中間節點、反轉鏈表、對比操作均遍歷鏈表一次，總時間與鏈表長度成正比。
• 空間復雜度：O (1)。僅使用有限個指針變量，未占用額外數據結構空間。

四、總結

本文通過 “快慢指針 + 反轉鏈表” 的經典思路，實現了鏈表回文結構的高效判斷。這種方法融合了鏈表操作的基礎技巧，是解決鏈表問題的常用范式。理解并掌握該解法，對提升鏈表算法能力有很大幫助，也可遷移到其他鏈表相關問題（如鏈表中點查找、鏈表反轉變形題）的解決中。

7. 力扣 160. 相交鏈表：函數實現深度解析

引言

在鏈表算法中，尋找兩個單鏈表的相交節點是經典問題。本文圍繞?getIntersectionNode?函數，詳細解析每一行代碼的實現邏輯，助讀者深入理解解法核心思想。

函數整體框架

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {  // 初始化指針與長度變量  ListNode* pa = headA;  ListNode* pb = headB;  int sizeA = 0, sizeB = 0;  // 計算鏈表長度  while (pa) { ... }  while (pb) { ... }  // 處理長度差，對齊鏈表  int gap = abs(sizeA - sizeB);  ListNode* shortList = headA;  ListNode* longList = headB;  if (sizeA > sizeB) { ... }  while (gap--) { ... }  // 同步遍歷找相交節點  while (shortList) { ... }  return NULL;  
}  

函數分為初始化、計算鏈表長度、處理長度差對齊鏈表、同步遍歷查找相交節點四部分，以下逐一解析。

1. 初始化指針與長度變量

ListNode* pa = headA;  
ListNode* pb = headB;  
int sizeA = 0, sizeB = 0;  

• 作用：定義?pa、pb?遍歷鏈表?headA、headB，sizeA、sizeB?記錄鏈表長度，為后續計算與操作奠基。
• 說明：指針初始化指向鏈表頭節點，長度變量置 0，便于后續累加。

2. 計算鏈表長度

while (pa) {  sizeA++;  pa = pa->next;  
}  
while (pb) {  sizeB++;  pb = pb->next;  
}  

• 計算鏈表 A 長度：
  • while (pa)?循環：pa?非空時，sizeA?自增 1（統計節點數），pa?后移。pa?為?NULL?時，完成遍歷，sizeA?存儲鏈表 A 長度。
• 計算鏈表 B 長度：
  • 邏輯同鏈表 A，通過?while (pb)?統計?sizeB，直至?pb?為?NULL。
• 意義：獲取兩鏈表長度，為后續長度差計算與鏈表對齊提供數據。

3. 處理長度差，對齊鏈表

int gap = abs(sizeA - sizeB);  
ListNode* shortList = headA;  
ListNode* longList = headB;  
if (sizeA > sizeB) {  longList = headA;  shortList = headB;  
}  
while (gap--) {  longList = longList->next;  
}  

• 計算長度差：
  • gap = abs(sizeA - sizeB)：用?abs?取長度差絕對值，確保?gap?非負。
• 確定長短鏈表指針：
  • if (sizeA > sizeB)?判斷鏈表長短。若 A 更長，longList?指向?headA，shortList?指向?headB；否則保持初始賦值。
• 長鏈表指針移動：
  • while (gap--)?循環：長鏈表指針?longList?后移?gap?步。如 A 比 B 長 3 步，longList?移動 3 步后，兩鏈表剩余部分長度一致，為找相交節點做準備。

4. 同步遍歷找相交節點

while (shortList) {  if (longList == shortList) {  return longList;  }  shortList = shortList->next;  longList = longList->next;  
}  
return NULL;  

• 遍歷查找：
  • while (shortList)?循環：shortList?非空時，檢查?longList?與?shortList?是否指向同一節點（地址相同）。若相同，找到相交節點，直接返回。
  • 未找到則?shortList、longList?同時后移，繼續遍歷。
• 返回結果：
  • 循環結束未找到相交節點，說明兩鏈表不相交，返回?NULL。

總結

getIntersectionNode?函數通過計算鏈表長度、處理長度差對齊鏈表、同步遍歷三步，高效解決相交鏈表問題。每一步目標明確，時間復雜度 O (M + N)，空間復雜度 O (1)，是簡潔高效的解法。理解函數實現細節，不僅掌握本題解法，更為解決其他鏈表問題提供思路。

8. 力扣 141 環形鏈表問題詳解：快慢指針法判斷鏈表是否有環

一、引言

在鏈表相關的算法問題中，“判斷鏈表是否有環” 是經典題目。本文將通過 C 語言實現，結合快慢指針算法，詳細解析每一行代碼的邏輯，幫助讀者深入理解解題思路。

---

二、算法思路

快慢指針法： 定義兩個指針，慢指針?slow?每次移動一步，快指針?fast?每次移動兩步。若鏈表有環，快指針最終會在環內追上慢指針（相遇）；若無環，快指針會先到達鏈表末尾（NULL）。

---

三、代碼實現（C 語言）

#include <stdbool.h>// 鏈表節點定義
struct ListNode {int val;struct ListNode *next;
};// 類型重命名，簡化代碼書寫
typedef struct ListNode ListNode;bool hasCycle(ListNode *head) {ListNode *slow, *fast;slow = fast = head; // 初始時，快慢指針都指向頭節點while (fast && fast->next) { // 快指針未到末尾時循環slow = slow->next;       // 慢指針每次移動一步fast = fast->next->next; // 快指針每次移動兩步if (fast == slow) {      // 快慢指針相遇，說明有環return true;}}return false; // 循環結束未相遇，說明無環
}

---

四、代碼逐行詳解

1. 鏈表節點定義

struct ListNode {int val;struct ListNode *next;
};
typedef struct ListNode ListNode;

• struct ListNode?定義鏈表節點，包含存儲值的?val?和指向下一節點的?next?指針。
• typedef?重命名類型，后續代碼中可用?ListNode?代替?struct ListNode，簡化書寫。

2. 函數參數與初始化

bool hasCycle(ListNode *head) {ListNode *slow, *fast;slow = fast = head;

• 函數?hasCycle?接收鏈表頭節點?head，返回布爾值（true?有環，false?無環）。
• 初始化快慢指針，均指向頭節點?head，從同一位置開始移動。

3. 循環條件

while (fast && fast->next) {

• fast && fast->next?確保快指針未到達鏈表末尾。若快指針為空或快指針的下一個節點為空，說明鏈表無環，退出循環。

4. 指針移動

slow = slow->next;
fast = fast->next->next;

• slow = slow->next;：慢指針每次沿?next?移動一步。
• fast = fast->next->next;：快指針每次移動兩步，加速遍歷。

5. 相遇判斷

if (fast == slow) {return true;
}

• 若快慢指針相遇（fast == slow），說明鏈表存在環，立即返回?true。

6. 最終返回結果

return false;

• 循環結束后未觸發相遇條件，說明鏈表無環，返回?false。

---

五、總結

快慢指針法通過不同的移動速度，高效判斷鏈表是否有環，時間復雜度為?\(O(n)\)，空間復雜度為?\(O(1)\)。理解這一思路后，不僅能解決本題，還能延伸到其他鏈表問題（如找環入口）。掌握指針操作和邏輯判斷，是解決鏈表問題的關鍵。

9. 力扣 142 環形鏈表 II 問題詳解：代碼逐行解析與算法原理深度剖析

引言

在鏈表相關的算法問題中，“環形鏈表 II” 是一個經典題目。給定鏈表頭節點?head，需要判斷鏈表是否有環，若有環則找到環的入口節點。本文將通過詳細的代碼解析和算法原理分析，帶大家深入理解這一問題的解決思路。

---

鏈表節點結構體定義

struct ListNode {int val;struct ListNode *next;
};
typedef struct ListNode ListNode;

• 結構體作用：定義單鏈表的節點結構。每個節點包含兩個成員，int val?用于存儲節點的值，struct ListNode *next?是指向下一個節點的指針，若?next?為?NULL，則表示當前節點是鏈表的尾節點。
• typedef?用途：通過?typedef?為?struct ListNode?定義別名?ListNode。這樣在后續代碼中，就可以直接使用?ListNode?代替?struct ListNode，簡化代碼書寫，讓代碼更簡潔易讀。

---

detectCycle?函數逐行解析

1. 函數初始化

struct ListNode* detectCycle(struct ListNode *head) {ListNode* slow = head;  // 慢指針，每次移動 1 步ListNode* fast = head;  // 快指針，每次移動 2 步

• 初始化快慢指針：定義兩個指針?slow（慢指針）和?fast（快指針），它們都從鏈表的頭節點?head?出發。慢指針每次移動一個節點，快指針每次移動兩個節點。這是利用快慢指針的速度差來判斷鏈表是否有環的經典初始化方式。若鏈表有環，快指針最終會追上慢指針（即相遇）；若鏈表無環，快指針會先到達鏈表末尾（NULL）。

2. 判斷鏈表是否有環

    while (fast && fast->next) {slow = slow->next;          // 慢指針移動 1 步fast = fast->next->next;    // 快指針移動 2 步if (fast == slow) {        // 快慢指針相遇，說明有環

• 循環條件：while (fast && fast->next)?確保快指針在移動時，fast?和?fast->next?都有效，避免指針越界。
• 指針移動邏輯：
  • slow = slow->next;：慢指針每次向前移動一個節點。
  • fast = fast->next->next;：快指針每次向前移動兩個節點。
• 環存在的判斷：當?fast == slow?時，快慢指針相遇，說明鏈表中存在環，此時進入尋找環入口節點的邏輯。

3. 尋找環入口節點

            ListNode* pcur = head;  // 新指針 pcur 從鏈表頭部出發while (slow != pcur) {  // 當 slow 和 pcur 未相遇時pcur = pcur->next;  // pcur 每次移動 1 步slow = slow->next;  // slow 繼續移動 1 步}return pcur;  // 相遇點即為環入口

• 數學原理支撐：設鏈表頭到環入口的距離為?a，環入口到快慢指針相遇點的距離為?b，環的周長為?c。相遇時，慢指針走過的距離是?a + b，快指針走過的距離是?a + b + n*c（n?為快指針繞環的圈數）。由于快指針速度是慢指針的 2 倍，可得?2(a + b) = a + b + n*c，化簡后得到?a = n*c - b。這表明，從鏈表頭（pcur）和相遇點（slow）同時出發，每次移動 1 步，最終會在環入口相遇。
• 代碼實現邏輯：
  • 定義新指針?pcur，使其從鏈表頭部?head?出發。
  • 通過?while (slow != pcur)?循環，讓?pcur?和?slow?每次各移動一個節點，直到兩者相遇。此時，pcur?指向的節點就是環的入口節點，直接返回該節點。

4. 處理無環情況

    }return NULL;  // 若循環結束未相遇，說明鏈表無環，返回 NULL
}

• 邏輯說明：如果?while (fast && fast->next)?循環正常結束（即快指針移動到鏈表末尾，fast?或?fast->next?為?NULL），說明鏈表中不存在環，此時直接返回?NULL。

---

算法總結

• 時間復雜度：整個算法中，快慢指針判斷環的過程和尋找環入口的過程，時間復雜度均為?\(O(n)\)，整體時間復雜度為?\(O(n)\)。
• 空間復雜度：僅使用了有限的指針變量，空間復雜度為?\(O(1)\)，沒有額外的空間消耗。
• 算法核心：利用快慢指針判斷鏈表是否有環，再通過數學推導找到環入口節點。這種方法巧妙地避免了使用哈希表等額外數據結構，高效解決了問題。

10. 力扣 138. 隨機鏈表的復制：函數級詳解與完整流程剖析

一、問題概述

復制帶有隨機指針?random?的鏈表時，需確保新鏈表的?next?和?random?指針均指向新鏈表節點。本文通過 “三步法” 實現，逐函數解析代碼邏輯。

---

二、代碼實現與函數詳解

1. 節點創建函數：buyNode

Node* buyNode(int x) {Node* newnode = (Node*)malloc(sizeof(Node));newnode->val = x;newnode->next = newnode->random = NULL;return newnode;
}

• 功能：動態分配內存創建節點，初始化?val，并將?next、random?置空。
• 細節：使用?malloc?分配內存，避免內存泄漏；初始化指針，防止野指針。
• 作用：為復制鏈表提供節點創建工具，后續復制的節點均由此生成。

2. 插入復制節點：AddNode

void AddNode(Node* head) {Node* pcur = head;while (pcur) {Node* newnode = buyNode(pcur->val);Node* next = pcur->next;newnode->next = next;pcur->next = newnode;pcur = next;}
}

• 執行流程：
  1. 遍歷原鏈表，對每個節點?pcur：
     • 創建值相同的復制節點?newnode。
     • 保存原節點的后續節點?next。
     • 將復制節點插入原節點后，形成?原節點->復制節點->原后續節點?結構。
  2. 遍歷完成后，鏈表變為原節點與復制節點交替排列。
• 核心作用：構建原節點與復制節點的相鄰關系，為處理?random?指針奠定結構基礎。

3. 設置隨機指針：setRandom

void setRandom(Node* head) {Node* pcur = head;while (pcur) {Node* copy = pcur->next;if (pcur->random) {copy->random = pcur->random->next;}pcur = copy->next;}
}

• 邏輯解析：
  • 遍歷原鏈表，copy?指向當前原節點的復制節點。
  • 若原節點?pcur?的?random?有指向，則其復制節點的?random?指向原?random?指向節點的復制節點（即?pcur->random->next）。
• 意義：利用原節點與復制節點的相鄰關系，精準定位復制節點?random?的指向，確保復制鏈表邏輯正確。

4. 主函數整合：copyRandomList

struct Node* copyRandomList(struct Node* head) {if (head == NULL) {return head;}AddNode(head);setRandom(head);Node* pcur = head;Node* copyHead = pcur->next;Node* copyTail = copyHead;while (copyTail->next) {pcur = copyTail->next;copyTail->next = pcur->next;copyTail = copyTail->next;}return copyHead;
}

• 執行步驟：
  1. 邊界檢查：原鏈表為空時直接返回。
  2. 插入復制節點：調用?AddNode?構建交替鏈表。
  3. 設置隨機指針：調用?setRandom?完善復制節點的?random。
  4. 拆分鏈表：
     • 提取復制鏈表頭節點?copyHead。
     • 遍歷調整復制節點的?next，使其指向后續復制節點，完成與原鏈表的分離。

---

三、算法總結

• 空間與時間：三次遍歷鏈表，時間復雜度 O (n)；利用原鏈表空間插入復制節點，空間復雜度 O (1)（除結果外）。
• 核心思想：通過插入節點構建關系，借助相鄰節點定位?random，最后拆分離出結果，是解決隨機鏈表復制的經典方法。