LeetCode 876. 链表的中间结点
题目描述
题意分析
返回链表的中间节点；长度为偶数时，中间有两个节点，要求返回后一个。若从 $0$ 开始编号，长度为
n的链表要返回的下标就是 $\lfloor n/2 \rfloor$。返回值是原链表中的节点引用，节点仍然连接后面的部分，不需要新建节点或截断链表。链表不能按下标直接访问，可以利用两个指针的速度差，在遍历过程中找到这个位置。
解法：快慢指针
核心思路
[!blue]
令
slow和fast都从头节点出发，每轮让slow走一步、fast走两步。完成k轮后，slow走了k步，fast走了2k步。因此用快指针判断何时到达链表末尾，就能让慢指针停在约一半的位置。循环条件是
fast和fast.next都非空：此时可以安全读取fast.next.next，它允许为空。退出时分两种情况：
- 长度为 $2m + 1$：执行
m轮后，fast位于最后一个节点，因其后继为空而停止；slow位于下标m，正是唯一中点。- 长度为 $2m$：执行
m轮后，fast恰好走到链表末尾之后，变为空；slow位于下标m，正是两个中点中的后一个。两种情况都让慢指针停在 $\lfloor n/2 \rfloor$，所以退出后直接返回
slow，不需要预先计算长度或单独处理奇偶。只有一个节点时，循环一次也不执行，返回头节点即可。
解题步骤
- 初始化
slow = head、fast = head。- 先判断
fast非空，再判断它的后继非空；两者都满足时，slow前进一步，fast前进两步。- 循环结束后返回
slow指向的节点。
代码实现
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)$，循环执行 $\lfloor n/2 \rfloor$ 轮，每轮只移动固定次数的指针。
- 空间复杂度：$O(1)$，只使用两个指针。
关键点总结
[!green]
- 完成
k轮后，慢指针前进k步、快指针前进2k步，速度差决定了中点位置。- 两个指针都从
head出发，配合当前循环条件，偶数长度时自然返回第二个中点。- 条件判断利用短路求值，必须先检查
fast，再访问fast.next。
易错点总结
[!yellow]
- 只判断
fast.next != null：偶数长度时fast会变成空，下一轮访问next发生空指针错误。- 把条件写成
fast.next != null && fast != null：判断顺序错误，短路求值无法保护空指针。- 将
fast初始化为head.next：在相同循环条件下，偶数长度时会少执行一轮，返回前一个中点。fast每轮只走一步：两个指针同速，slow最终不会停在中点。- 返回
slow.val：题目要求的是节点引用，而不是节点值。- 修改
slow.next：题目只要求定位节点，不能为了返回中点而切断原链表。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 2095. 删除链表的中间节点 | 中等 | 原题删掉中点，需要让慢指针停在中点前驱，本题只返回中点本身。 |
| 143. 重排链表 | 中等 | 找中点是拆分链表的基础，原题之后反转后半段再交错连接。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！