📑 本页目录（点开跳转）
01 · 链表：指针到底在保住什么
⏱ 12 分钟 ｜ 反转、合并、环入口：全是“先别把下一站弄丢”
🎯 一句话
链表题的核心不是指针语法，而是：改 next 之前，先把旧的下一站存下来。
🧩 题 1：反转链表
题目。 1 → 2 → 3 变成 3 → 2 → 1。
先画。 prev 是已经翻好的部分；cur 是还没处理的第一个节点；nxt 临时保住后路。
不变量。 每轮结束后，prev 指向已反转的前缀，cur 指向尚未处理的后缀。
class ListNode:
def __init__(self, val, next=None):
self.val, self.next = val, next
def reverse_list(head):
prev, cur = None, head
while cur:
nxt = cur.next # 先保住后路
cur.next = prev # 再掉头
prev, cur = cur, nxt # 两队伍一起向前
return prev
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
head = ListNode(1, ListNode(2, ListNode(3)))
assert values(reverse_list(head)) == [3, 2, 1]
⚠️ 最常见的错：先写 cur.next = prev，再想找原来的 cur.next。这时后路已经被覆盖，节点就丢了。
🧩 题 2：合并两个有序链表
题目。 把 1 → 3 → 5 和 2 → 4 合成 1 → 2 → 3 → 4 → 5。
不变量。 tail 后面永远是已经排好序的结果；a、b 各自指向还没被拿走的最小节点。
class ListNode:
def __init__(self, val, next=None):
self.val, self.next = val, next
def merge_sorted(a, b):
dummy = ListNode(0)
tail = dummy
while a and b:
if a.val <= b.val:
tail.next, a = a, a.next
else:
tail.next, b = b, b.next
tail = tail.next
tail.next = a or b
return dummy.next
def values(head):
out = []
while head:
out.append(head.val)
head = head.next
return out
a = ListNode(1, ListNode(3, ListNode(5)))
b = ListNode(2, ListNode(4))
assert values(merge_sorted(a, b)) == [1, 2, 3, 4, 5]
💡 dummy 只是一个假头：这样第一个节点也和后面的节点一样接，不必写“第一次特殊处理”。
🧩 题 3：链表中环的入口
题目。 链表可能绕回去。返回绕回的第一个节点；没有环则返回 None。
先想两段路。 快慢指针相遇说明有环。相遇后，让一个指针回头；两者都每次走一步，再次相遇的地方就是入口。
class ListNode:
def __init__(self, val, next=None):
self.val, self.next = val, next
def cycle_entry(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
break
else:
return None
seeker = head
while seeker is not slow:
seeker, slow = seeker.next, slow.next
return seeker
n1, n2, n3, n4 = ListNode(1), ListNode(2), ListNode(3), ListNode(4)
n1.next, n2.next, n3.next, n4.next = n2, n3, n4, n2
assert cycle_entry(n1) is n2
这里不需要背距离公式。先记住使用条件：一个快、一个慢能确认“是否绕圈”；确认后，同速从头和相遇点出发能找到入口。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| Python 会咬你的地方 01 · 名字、对象和绑定 | ⭐ 「先保住后路再掉头」为什么必须这么写：Python 里赋值从不复制对象，只是把名字重新贴一次。prev, cur = cur, nxt 这种多重赋值的求值顺序也在那一章 |
🛑 可以停在这里
链表所有“改指针”的题，先问：我改掉这条线之前，下一站放哪了？
✅ 检查点
反转链表时为什么一定先保存 nxt？
👀 看答案
因为下一步会覆盖 cur.next。不先保存，原来尚未处理的后缀就再也找不到了。
⚡ 走神救援
- 反转：
nxt保后路，prev是已翻好的头。 - 合并：
tail后面始终有序，dummy消灭首节点特判。 - 环入口：快慢先相遇；一个回头后，两人同速再见就是入口。