快慢双指针

快慢指针：876 链表的中间结点

1. 前提条件
   题目给你一个单链表：
   1 -> 2 -> 3 -> 4 -> 5
   要求返回：中间结点

如果有两个中间结点，返回第二个。

例如：1 -> 2 -> 3 -> 4 -> 5

返回：3

如果：1 -> 2 -> 3 -> 4 -> 5 -> 6

中间有：3 和 4

题目要求返回第二个：4

2. 核心概念：快慢指针

定义两个指针：

slow = head;
fast = head;

每次：

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

也就是：

slow 每次走一步
fast 每次走两步

当 fast 到达末尾时：slow 正好在中间。

3. 为什么 slow 会到中间？

因为：fast 的速度是 slow 的 2 倍。

如果 fast 走完整条链表，slow 就走了一半。

4. 代码模板
   struct ListNode* middleNode(struct ListNode* head) {
   struct ListNode* slow = head;
   struct ListNode* fast = head;

   while (fast != NULL && fast->next != NULL) {
   slow = slow->next;
   fast = fast->next->next;
   }

   return slow;
   }

5. 奇数长度例子
   1 -> 2 -> 3 -> 4 -> 5

初始：slow = 1 fast = 1

第一轮：slow = 2 fast = 3

第二轮：slow = 3 fast = 5

再下一轮：fast->next == NULL

停止。

返回：slow = 3
6. 偶数长度例子
1 -> 2 -> 3 -> 4 -> 5 -> 6

初始：slow = 1 fast = 1

第一轮：slow = 2 fast = 3

第二轮：slow = 3 fast = 5

第三轮：slow = 4 fast = NULL

停止。

返回：slow = 4

这就是第二个中间结点。

7. while 条件
   while (fast != NULL && fast->next != NULL)

因为循环里有：

fast = fast->next->next;

所以必须保证：

fast 不为空
fast->next 不为空

否则访问：fast->next->next

可能出错。

8. 快慢指针题型总结

快慢指针：slow 每次走一步,fast 每次走两步

用途：

1. 找链表中点
2. 判断链表是否有环
3. 找环入口
4. 回文链表
5. 链表归并排序找中点
   刚刚看的是最简单的问题，接下来我们看一下回文链表和链表回退k步的问题:
   快慢双指针多用于解决无法统计次数的循环问题，否则一旦有总的循环次数n，直接对应就能找到位置

一、142 环形链表 II

1. 前提条件

题目给一个链表：

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

要求：

如果链表有环，返回环的入口节点；
如果没有环，返回 NULL。

例如：

3 -> 2 -> 0 -> -4
↑ ↓
← ← ← ← ← ←

环入口是：节点 2

2. 核心概念

快慢指针：

slow 每次走 1 步
fast 每次走 2 步

如果链表有环：fast 一定会在环内追上 slow。

相遇后：

一个指针回到 head；
另一个指针留在相遇点；
两个指针每次都走 1 步；
再次相遇的位置就是环入口。

3. 为什么能找到入口？

设：

head 到环入口距离 = a
环入口到相遇点距离 = b
相遇点再回到入口距离 = c

图：

head ---- a ---- entry ---- b ---- meet
↑ |
|---- c ----|

slow 走的距离：

a + b

fast 走的距离：

a + b + k(b + c)

因为 fast 速度是 slow 的 2 倍：

fast 距离 = 2 * slow 距离

所以：

a + b + k(b + c) = 2(a + b)

化简可得到：

a = k(b + c) - b

也就是：

a = (k - 1)(b + c) + c

意思是：

从 head 到入口的距离 a
等价于

从相遇点走 c 再绕若干圈到入口。

所以：

一个从 head 走；
一个从 meet 走；
每次都走一步；
它们会在入口相遇。

相遇后，一个回 head，一个留 meet，同速走，相遇点就是入口。

4. 固定模板
   struct ListNode detectCycle(struct ListNode head) {
   struct ListNode slow = head;
   struct ListNode fast = head;
   //先都定位到head头
   while (fast != NULL && fast->next != NULL) {
   slow = slow->next;
   fast = fast->next->next;
   //之后分配步调，slow走一步，fast走两步
   if (slow == fast) {
   struct ListNode* p1 = head;
   struct ListNode* p2 = slow;
   //一旦相遇之后把p1再定位到head，然后p2定位到meet的地点，循环往后走直到相遇就是入口的位置
   while (p1 != p2) {
   p1 = p1->next;
   p2 = p2->next;
   }

        return p1;
    }
   

   }

   return NULL;
   }

5. 例题流程

链表：

3 -> 2 -> 0 -> -4
↑ ↓
← ← ← ← ←

也就是：

3 -> 2 -> 0 -> -4
^ |
|_________|

初始：

slow = 3
fast = 3

第一轮：

slow = 2
fast = 0

第二轮：

slow = 0
fast = 2

第三轮：

slow = -4
fast = -4

相遇。

然后：

p1 = head = 3
p2 = meet = -4

一起走。

第一步：

p1 = 2
p2 = 2

相遇在节点 2。

所以返回：2是环入口。

6. 易错点
   易错点 1：while 条件必须写完整
   while (fast != NULL && fast->next != NULL)

因为循环里有：

fast = fast->next->next;

所以必须保证：

fast 不为空；
fast->next 不为空。

易错点 2：判断相遇要比较指针，不是比较值

正确：if (slow == fast)

错误：if (slow->val == fast->val)

因为链表里不同节点可能值一样。

易错点 3：相遇点不一定是入口

第一次相遇的位置通常不是入口。

必须再做：

p1 = head
p2 = meet
一起走

才能找入口。

7. 总结
   142 环形链表 II

8. slow、fast 从 head 出发。

9. slow 每次 1 步，fast 每次 2 步。

10. 如果 fast 或 fast->next 为 NULL，说明无环。

11. 如果 slow == fast，说明有环。

12. 一个指针回 head，另一个留在相遇点。

13. 两个指针每次走 1 步。

14. 再次相遇处就是环入口。

快慢指针负责判断是否有环；相遇后双指针同速走负责找入口。

接下来看一下另一个题目：19 删除链表的倒数第 N 个结点

1. 前提条件
   题目给一个链表和整数 n：

1 -> 2 -> 3 -> 4 -> 5
n = 2

要求删除倒数第 n 个节点。

倒数第 2 个是：4

删除后：

1 -> 2 -> 3 -> 5

2. 核心概念
   用两个指针：
   fast
   slow

让 fast 先走 n 步。

然后：

fast 和 slow 一起走。

当 fast 到达链表末尾时：

slow 正好在要删除节点的前一个位置。

3. 为什么要用 dummy 虚拟头结点？

如果要删除的是头节点，比如：

1 -> 2 -> 3
n = 3

倒数第 3 个就是：1

如果没有虚拟头结点，删除头节点比较麻烦。

所以创建：

dummy -> 1 -> 2 -> 3

最后返回：

dummy->next
这样所有情况统一处理。

4. C代码：
   #include <stdlib.h>

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode* dummy =
malloc(sizeof(struct ListNode));

dummy->next = head;

struct ListNode* fast = dummy;
struct ListNode* slow = dummy;

for (int i = 0; i < n; i++) {
    fast = fast->next;
}

//先让fast走n步，之后两者一块走
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
//走到尽头之后，slow的下一个位置就是需要的，然后把slow的下一个位置的next扔给slow的next连接就好
slow->next=slow->next->next;

struct ListNode* ans = dummy->next;
free(dummy);

return ans;

}
5. 例题流程

链表：1 -> 2 -> 3 -> 4 -> 5
n = 2

加 dummy：

dummy -> 1 -> 2 -> 3 -> 4 -> 5

初始：

fast = dummy
slow = dummy
fast 先走 2 步

第一步：

fast = 1

第二步：

fast = 2

此时：

fast 和 slow 相隔 2 个节点。
两个一起走

当前：

slow = dummy
fast = 2

循环条件：

while (fast->next != NULL)

第一轮：

slow = 1
fast = 3

第二轮：

slow = 2
fast = 4

第三轮：

slow = 3
fast = 5

此时：

fast->next == NULL

停止。

现在：

slow = 3

要删除的节点是：

slow->next = 4

执行：

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

变成：

1 -> 2 -> 3 -> 5
6. 为什么 slow 会停在删除节点前面？

因为：

fast 比 slow 领先 n 个节点。

当 fast 到达最后一个节点时：

slow->next

正好是倒数第 n 个节点。

所以删除：slow->next即可。

7. 删除头节点例子

链表：

1 -> 2 -> 3
n = 3

加 dummy：

dummy -> 1 -> 2 -> 3

fast 先走 3 步：

fast = 3
slow = dummy

此时：

fast->next == NULL

不进入 while。

所以：

slow = dummy

删除：

slow->next = 1

执行：

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

结果：

2 -> 3

最后返回：

dummy->next

正好是新头节点 2。

8. 易错点
   易错点 1：不用 dummy 会难处理删除头节点

例如：

1 -> 2 -> 3
n = 3

要删头节点。

用 dummy 最稳。

易错点 2：fast 先走 n 步，不是 n+1 步

在这个写法里：

fast 和 slow 都从 dummy 开始
fast 先走 n 步
while(fast->next != NULL)

这样 slow 最后停在删除节点前一个。

易错点 3：删除节点前要保存
struct ListNode* deleteNode = slow->next;
slow->next = deleteNode->next;
free(deleteNode);

如果是 LeetCode，有些人不 free 也能过，但 C 语言最好写完整。

易错点 4：最后返回 dummy->next

不能返回原来的 head。

因为如果删的是头节点，head 已经被删掉了。

9. 总结
   19 删除链表倒数第 N 个节点

核心：让 fast 先走 n 步。

然后 fast 和 slow 同时走。

当 fast 到尾部时，

slow 在待删除节点前一个位置。

---

为什么用 dummy：

统一处理删除头节点的情况。

---

返回：

dummy->next

快慢指针通过保持 n 个节点的距离，把“倒数第 n 个”转化成“slow 的下一个节点”。