数据结构C语言练习(单双链表)

本篇练习题(单链表)：

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，最后拆分离出结果，是解决随机链表复制的经典方法。