016 · Middle of the Linked List

My First Thoughts

这道题又是一个链表问题。

题目要求返回中间节点，不是返回中间节点的值。

也就是说，如果链表是：

1 -> 2 -> 3 -> 4 -> 5 -> None

答案不是数字 3，而是从节点 3 开始的这段链表：

3 -> 4 -> 5 -> None

第一反应会是：那我是不是先把链表完整走一遍？

比如一边走，一边把节点记录下来：

[node1, node2, node3, node4, node5]

然后看长度。

如果长度是奇数，比如 5，中间下标是：

5 // 2 = 2

也就是返回 nodes[2]。

如果长度是偶数，比如 6，题目说要返回第二个中间节点：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

两个中间节点是 3 和 4，要返回 4。

而：

6 // 2 = 3

刚好也是第二个中间节点的下标。

所以一个直接做法是：把所有节点放进数组，然后返回 nodes[len(nodes) // 2]。

这个想法可以做出来，而且不难。

---

Why That Is Not Enough

记录所有节点的问题是：需要额外空间。

如果链表有 n 个节点，数组里也要存 n 个节点引用，所以空间复杂度是 \(O(n)\)。

但这道题其实只需要找到中间位置，不需要保留所有节点。

换句话说，我们关心的是：

什么时候走到链表中间？

而不是：

链表里每一个节点分别是什么？

这里可以用两个指针控制速度：

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

当 fast 走到链表末尾时，slow 只走了它一半的路程，所以 slow 正好停在中间节点。

这也是快慢指针的典型用法。

---

Final Idea

从 head 开始，让 slow 和 fast 都指向链表头节点。

每一轮循环：

1. slow 向后走一步
2. fast 向后走两步

只要 fast 还能继续走两步，就继续循环：

while fast and fast.next:

当循环结束时，fast 已经到达链表末尾，或者已经越过末尾。

这时 slow 指向的就是中间节点，直接返回 slow。

以奇数长度为例：

1 -> 2 -> 3 -> 4 -> 5 -> None

移动过程是：

slow: 1 -> 2 -> 3
fast: 1 -> 3 -> 5

fast 到达最后一个节点时，slow 在 3。

以偶数长度为例：

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None

移动过程是：

slow: 1 -> 2 -> 3 -> 4
fast: 1 -> 3 -> 5 -> None

fast 越过链表末尾时，slow 在 4。这正好是题目要求的第二个中间节点。

---

Why It Works

fast 的速度是 slow 的两倍。

所以当 fast 走完整条链表时，slow 走过的距离正好是链表长度的一半。

如果链表长度是奇数，slow 会停在唯一的中间节点。

如果链表长度是偶数，循环条件 while fast and fast.next 会让 slow 多走到第二个中间节点。

因此最后返回 slow，就是题目要求的中间节点。

---

Code

def middleNode(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

---

Complexity

Time	\(O(n)\) — fast 最多走完整条链表
Space	\(O(1)\) — 只用了两个额外指针

---

Takeaway

找链表中点时，不一定要先记录所有节点。让一个指针走一步、另一个指针走两步，快指针到尾部时，慢指针就停在中间。

---

← Quiz