链表核心操作

2026-06-02

链表所有错都从一句话来：改 cur.next 之前,先把 cur.next 存下来,否则后面那一截就丢了。记住这句,再配 dummy / 双指针 / 头插反转三招,80% 链表题就是模板题。

直觉 — 断开前先保存 next

链表和数组最大的区别: 数组随便改一个位置, 别的元素不会消失; 链表你改了 cur.next, 原来那条链就立刻断了, 没有第二条路再走回去。

1
cur.next = prev    # 这一行执行完, 原来的 cur.next 就再也找不到了

所以模板的第一行永远是 nxt = cur.next。三步口诀:

  1. 存 — nxt = cur.next(救命绳)
  2. 转 — cur.next = prev(动手术)
  3. 移 — prev = cur; cur = nxt(往前挪)

下面动画把这三步在 5 节点链表上演示一轮。重点盯三个指针: 黄色 cur、青色 prev、红色 nxt。每点一次”下一步”,看哪个箭头翻向了哪边。红色 nxt 出现的那一帧,就是”存”在救你命。

三大套路 — dummy / 双指针 / 头插反转

1. dummy 头节点 — 头会变就用它

凡是头节点可能被删/换/合的题(反转、合并、删除、分组),开局就 dummy = ListNode(0, head),最后返回 dummy.next。代价: 多一个节点。收益: 不写 if head is None 也不写 if node == head 的特判。

什么时候不用: 只遍历、只改值、不动结构(比如统计长度、找中点)。

2. 双指针 — 一招吃三题

场景 配方
找中点 slow 走 1 步, fast 走 2 步, fast 到尾 → slow 在中间
检测环 slow 1 步、fast 2 步, 相遇 = 有环, 永远碰不上 = 无环
倒数第 k 个 fast 先走 k 步, 然后两者同步走, fast 到尾 → slow 在倒数第 k

为什么有效: 两个指针速度差让”距离”成了可以利用的量。找中点是用”2 倍速到尾”换”1 倍速到半”,倒数第 k 是用”领先 k 步”换”落后 k 个位置”。

3. 头插法反转 — 不只反转链表

1
2
3
4
5
# 把 cur 拆下来, 插到 dummy 后面
nxt = cur.next
cur.next = dummy.next
dummy.next = cur
cur = nxt

每次把当前节点摘下来塞到 dummy 后面, 自动倒序。反转一段区间(LC 92)、K 个一组反转(LC 25) 都是这套头插的变体。

模板 — Python

反转整条链表:

1
2
3
4
5
6
7
8
def reverseList(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next      # 存
        cur.next = prev     # 转
        prev = cur          # 移
        cur = nxt           # 移
    return prev             # prev 是新头

合并两个有序链表:

1
2
3
4
5
6
7
8
9
10
def mergeTwoLists(l1, l2):
    dummy = tail = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2    # 接上剩下的那条
    return dummy.next

检测环 + 找入口(Floyd):

1
2
3
4
5
6
7
8
9
10
11
12
13
def detectCycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None         # 无环
    # 找入口
    p = head
    while p is not slow:
        p, slow = p.next, slow.next
    return p

Floyd 环检测背后的数学

为什么”相遇后,一个回起点同速走,再次相遇即是入口”? 一张图能讲清:

1
2
3
4
5
起点 ──── a ────► 入口 ──── b ────► 相遇点
                  ▲                    │
                  │                    │
                  └────── c ───────────┘
        (环长 L = b + c)

设起点到入口距离 ,入口到相遇点 ,相遇点继续走 回到入口(所以环长 )。

相遇时:

  • slow 走了
  • fast 走了 (在环里多绕了 圈)
  • fast 速度是 slow 两倍:

化简: , 即 。

翻译: 从起点走 步到入口, 等价于从相遇点走 步再绕 圈也到入口。所以两个指针一个从起点、一个从相遇点,同速走,必然在入口相遇。

记住一句: a = c (mod L)。剩下的全靠肌肉记忆。

经典题

热身(纯模板):

进阶(套路组合):

判回文不开数组: 找中点 → 反转后半 → 双指针对比。三个核心操作一题用全。

记忆法

一句话: 改指针之前先存 next, 头会变就上 dummy, 想找位置就开俩指针。

三个对仗:

问题 套路
头节点可能变 dummy
要找”半路上”的位置 双指针(速度差或距离差)
要倒序 / 反转一段 头插法到 dummy 后面

Floyd 环检测就背一句: a = c (mod L) — 起点到入口 = 相遇点到入口(模环长)。剩下的就是动手画图。链表题不画图直接写指针 = 必错,这条铁律永远不要破。