LeetCode 876. 链表的中间结点
目录
题目描述
题意分析
给定一条单链表的头节点，要求返回位于正中间的那个节点本身（不是它的值，也不是下标），并且返回的节点还带着它后面的整条链。
题意里唯一需要仔细读的是奇偶之分。长度为奇数时中点唯一；长度为偶数时正中间有两个节点，题目明确规定返回靠后的那个。比如 $6$ 个节点时返回第 $4$ 个而不是第 $3$ 个。这条规则决定了后面所有实现细节的取舍，读错就会整体偏移一位。
约束很宽松：节点数在 $1$ 到 $100$ 之间，说明头节点一定非空，不必处理空链表；数据规模也完全不构成压力，因此这道题考的不是效率极限，而是能否只遍历一趟、只用常数空间写对。
边界有三个：只有一个节点时中点就是它自己；只有两个节点时按规则返回第二个；三个节点时返回正中间那个。这三种情况足以暴露绝大多数写法上的偏移错误。
解法：快慢指针
核心思路
两趟扫描可以先求长度再定位中点，但快慢指针能在一趟内完成：
slow每轮走一步，fast每轮走两步，两者都从head出发。当fast无法继续走两步时，slow正好走了链表长度的一半。不变量是：完成 $t$ 轮后，
slow从头移动了 $t$ 步，fast移动了 $2t$ 步。循环共执行 $\lfloor n/2 \rfloor$ 轮，因此slow最终位于从零开始的下标 $\lfloor n/2 \rfloor$；奇数长度时是唯一中点，偶数长度时是第二个中点，恰好符合题意。循环条件必须同时保证
fast和fast.next非空。退出后无需判断链表长度的奇偶，直接返回slow。
解题步骤
- 初始化
slow = head、fast = head。- 当
fast != null && fast.next != null时，slow前进一步，fast前进两步。- 循环结束后返回
slow指向的节点。例如
[1,2,3,4,5]经过两轮后，slow指向 $3$；[1,2,3,4,5,6]经过三轮后，slow指向第二个中点 $4$。单节点链表不进入循环，直接返回头节点。
代码实现
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
func middleNode(head *ListNode) *ListNode {
slow := head
fast := head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
复杂度分析
- 时间复杂度：$O(n)$，链表只遍历一趟。
- 空间复杂度：$O(1)$，只使用两个指针。
关键点总结
- 快指针速度是慢指针的两倍，因此快指针到达末尾时，慢指针位于中点。
- 两个指针都从
head出发，才能在偶数长度时返回第二个中点。- 条件判断利用短路求值，必须先检查
fast，再访问fast.next。- 若追问前一个中点，可让
fast从head.next出发；该技巧也常用于回文链表、重排链表等题目。
易错点总结
- 只判断
fast.next != null：偶数长度时fast会变成空，下一轮访问next发生空指针错误。- 把条件写成
fast.next != null && fast != null：判断顺序错误，短路求值无法保护空指针。- 将
fast初始化为head.next：[1,2,3,4]会返回前一个中点 $2$，而题目要求 $3$。fast每轮只走一步：两个指针同速，slow最终不会停在中点。- 返回
slow.val：题目要求的是节点引用，而不是节点值。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 19. 删除链表的倒数第 N 个结点 | 中等 | 固定间距双指针删点 |
| 141. 环形链表 | 简单 | 快慢指针判环 |
| 142. 环形链表 II | 中等 | 快慢指针求环入口 |
| 143. 重排链表 | 中等 | 找中点后断开重组 |
| 234. 回文链表 | 简单 | 找中点后反转比较 |
| 剑指 Offer 22. 链表中倒数第k个节点 | 简单 | 倒数第 k 个节点 |