LeetCode876/141/142/143 快慢指针应用：链表中间 / 环形 / 重排问题

目录

一、876. 链表的中间节点（快慢指针基础）

题目核心

核心难点拆解

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

易踩坑点 & 底层原理

二、141. 环形链表（判环的必然性）

题目核心

核心难点拆解

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

易踩坑点 & 底层原理

三、142. 环形链表 II（环入口的数学推导）

题目核心

核心难点拆解

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

易踩坑点 & 底层原理

四、143. 重排链表（快慢指针 + 反转 + 合并的组合）

题目核心

核心难点拆解

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

易踩坑点 & 底层原理

五、跨题深度对比：快慢指针的应用边界

快慢指针的通用应用场景

进阶思考

这四道题是快慢指针在链表中的经典应用，从基础定位（中间节点）到环检测（是否有环、环入口），再到组合操作（重排链表），核心逻辑均围绕 “标签（指针）的速度差” 展开。本次聚焦底层原理、必踩坑点、代码关键细节，用「盒子（节点）、标签（指针）、纸条（next）」模型分析 “为什么这么设计”。

一、876. 链表的中间节点（快慢指针基础）

题目核心

给定非空链表，返回中间节点；若有两个中间节点，返回第二个（如1→2→3→4→5返回 3，1→2→3→4返回 3）。

核心难点拆解

1. 为什么快指针走 2 步、慢指针走 1 步？快慢指针的速度比为 2:1，当快指针到达链表末尾时，慢指针恰好走了链表长度的一半 —— 这是 “定位中间” 的核心逻辑，本质是利用速度差实现 “一次遍历定位中间”（避免先统计长度再遍历的 O (2n) 操作）。
2. 偶数长度时，为什么 slow 停在第二个中间节点？以1→2→3→4为例：
   • fast 初始在 1，依次走 2→4→null；
   • slow 初始在 1，依次走 2→3；当 fast 走到 null 时，slow 恰好停在第二个中间节点（3），符合题目要求。
3. 奇数长度时，slow刚好停在正中间的节点。

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

class Solution { public ListNode middleNode(ListNode head) { // 关键点1：快慢标签均从head盒子出发 ListNode slow = head; ListNode fast = head; // 关键点2：循环条件双层防御——避免fast或fast.next为null时的空指针 // 若写“fast != null”，当fast在最后一个盒子时，fast.next为null，执行fast.next.next会报错 while (fast != null && fast.next != null) { slow = slow.next; // slow标签移动1个盒子 fast = fast.next.next; // fast标签移动2个盒子 } // 关键点3：fast到末尾时，slow恰好停在中间盒子 return slow; } }

易踩坑点 & 底层原理

• 坑 1：循环条件仅写fast != null→ 当链表长度为偶数时，fast.next为 null，执行fast.next.next会空指针；
• 坑 2：快慢指针初始位置不一致（如 slow 从 head，fast 从 head.next）→ 会导致中间节点定位偏移；
• 原理：快慢指针的速度比决定了 “相对位移”，2:1 的速度比是定位中间节点的唯一最优解（其他比例无法精准定位）。

二、141. 环形链表（判环的必然性）

题目核心

判断链表是否存在环（即某个节点的next指向之前的节点，形成循环）。

核心难点拆解

1. 为什么有环的话，快慢指针一定会相遇？若链表有环，快慢指针进入环后会持续绕圈：
   • slow 速度 1，fast 速度 2，相对速度为 1（fast 每次比 slow 多走 1 个节点）；
   • 相当于 slow 静止，fast 以速度 1 向 slow 靠近，因此必然会追上（不会永远追不上）。
2. 为什么 fast 不能走 3 步 / 4 步？若 fast 速度为 3，相对速度为 2，可能会 “跳过” slow（如环长为 2 时，fast 和 slow 的位置差始终为奇数，无法相遇）——2 步是唯一能保证相遇的速度。

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

public class Solution { public boolean hasCycle(ListNode head) { // 关键点1：空链表/单节点链表无环，直接返回 if (head == null || head.next == null) return false; // 关键点2：快慢标签初始位置错开（避免初始状态slow==fast） ListNode slow = head; ListNode fast = head.next; // 关键点3：若fast追上slow，则有环；若fast到末尾，则无环 while (slow != fast) { // 无环的终止条件：fast或fast.next为null if (fast == null || fast.next == null) return false; slow = slow.next; fast = fast.next.next; } // 退出循环说明slow==fast，有环 return true; } }

易踩坑点 & 底层原理

• 坑 1：快慢标签初始位置相同（均为 head）→ 循环条件slow != fast会直接跳过初始检查，误判无环；
• 坑 2：循环条件写fast != null→ 当 fast 在环内时，永远不会为 null，导致死循环；
• 原理：相对速度为 1是快慢指针相遇的核心前提，速度差过大可能导致 “追及失败”。

三、142. 环形链表 II（环入口的数学推导）

题目核心

若链表有环，返回环的入口节点；若无环，返回 null（如3→2→0→-4→2，环入口是 2）。

核心难点拆解

1. 环入口的数学推导（最核心）：定义：

   • a：头节点到环入口的盒子数；
   • b：环入口到快慢指针相遇点的盒子数；
   • c：相遇点到环入口的盒子数；
   • 环长：L = b + c。

   快慢指针的路程关系：

   • slow 走了a + b（到相遇点）；
   • fast 走了a + b + nL（绕了 n 圈后相遇）；
   • 因 fast 速度是 slow 的 2 倍，故2(a + b) = a + b + nL→ 化简得a = c + (n-1)L。

   结论：头节点到环入口的距离 = 相遇点到环入口的距离 + (n-1) 圈环长→ 因此让一个标签从头节点出发，一个从相遇点出发，同速移动，会在环入口相遇。

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

public class Solution { public ListNode detectCycle(ListNode head) { // 步骤1：找快慢指针的相遇点 ListNode slow = head; ListNode fast = head; boolean hasCycle = false; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { // 找到相遇点 hasCycle = true; break; } } // 无环直接返回 if (!hasCycle) return null; // 步骤2：找环入口——核心逻辑 ListNode ptr1 = head; // 从头节点出发的标签 ListNode ptr2 = slow; // 从相遇点出发的标签 while (ptr1 != ptr2) { ptr1 = ptr1.next; // 同速移动（每次1个盒子） ptr2 = ptr2.next; } // 相遇时即为环入口 return ptr1; } }

易踩坑点 & 底层原理

• 坑 1：推导时忽略nL（绕圈次数）→ 误以为a = c，但实际 n≥1 时仍成立（绕圈不影响最终相遇）；
• 坑 2：找相遇点后直接返回 slow → 相遇点不是环入口，需二次移动；
• 原理：a = c + (n-1)L是环入口的数学本质，同速移动的标签会在 “环入口” 抵消绕圈的影响。

四、143. 重排链表（快慢指针 + 反转 + 合并的组合）

题目核心

将链表L0→L1→…→Ln-1→Ln重排为L0→Ln→L1→Ln-1→…（如1→2→3→4→1→4→2→3）。

核心难点拆解

1. 为什么拆分为 “找中间 + 反转后半段 + 合并”？重排的本质是 “前半段与反转后的后半段交替拼接”，因此需要：
   • 找中间：将链表拆分为L0→L1和L2→L3（偶数长度）；
   • 反转后半段：将L2→L3转为L3→L2；
   • 合并：L0→L3→L1→L2。
2. 拆分后必须断开链表的原因？若不断开前半段与后半段的连接（如1→2→3→4不把 2 的 next 设为 null），反转后半段后会形成环（3 的 next 指向 2），导致合并时死循环。

深度思路（盒子 - 标签 - 纸条模型）

代码实现（带关键点标注）

class Solution { public void reorderList(ListNode head) { // 边界防御：空链表/单节点无需处理 if (head == null || head.next == null) return; // 步骤1：找中间节点，拆分链表 ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode mid = slow.next; // 后半段头盒子 slow.next = null; // 关键点1：断开前半段与后半段，避免环 // 步骤2：反转后半段 ListNode reversedMid = reverse(mid); // 步骤3：合并前半段与反转后的后半段 merge(head, reversedMid); } // 反转链表（辅助方法） private ListNode reverse(ListNode head) { ListNode prev = null; ListNode cur = head; while (cur != null) { ListNode temp = cur.next; cur.next = prev; // 反转纸条方向 prev = cur; cur = temp; } return prev; } // 交替合并两个链表（辅助方法） private void merge(ListNode p1, ListNode p2) { while (p1 != null && p2 != null) { ListNode temp1 = p1.next; // 暂存前半段下一个盒子 ListNode temp2 = p2.next; // 暂存后半段下一个盒子 p1.next = p2; // 前半段盒子连接后半段盒子 p2.next = temp1; // 后半段盒子连接前半段下一个盒子 p1 = temp1; // 移动标签 p2 = temp2; } } }

易踩坑点 & 底层原理

• 坑 1：拆分链表时未断开slow.next→ 反转后半段后形成环，合并时死循环；
• 坑 2：合并时未暂存next→ 直接修改p1.next会丢失原链表的后续盒子；
• 原理：重排是 “基础操作的组合”，快慢指针定位中间是前提，反转是核心，合并是收尾，三者缺一不可。

五、跨题深度对比：快慢指针的应用边界

快慢指针的通用应用场景

1. 定位类：找中间节点、找倒数第 k 个节点（快指针先移 k 步）；
2. 环操作类：判断环、找环入口；
3. 组合操作类：作为拆分链表的前置步骤（如重排链表）。

进阶思考

• 若链表是双向链表，判环 / 找入口的方法会简化吗？→ 可以直接记录访问过的节点，无需快慢指针，但空间复杂度从 O (1) 变为 O (n)；
• 重排链表的时间复杂度是多少？→ 找中间 O (n) + 反转 O (n) + 合并 O (n)，总时间 O (n)，空间 O (1)（原地操作）。