S03-J03 · 链表操作：指针的四种基本动作

适用读者：链表题每次都要现场推指针、写完自己也不确定对不对的人。
前置：S03-B02（数组与链表）。
实测环境：Python 3.12.3（迭代/递归反转对比）；实测日期 2026-11-05。
覆盖旧文：2、19、21、23、24、25、61、82、83、86、92（11 张卡，2,168 点）。
覆盖扩展：E-S03-017（虚拟头 + 三指针模板）。
补写：#24、#61、#82（空壳卡，E-S03-114~E-S03-116）。
上一篇：S03-J02 · 二分查找：边界、旋转与答案二分
下一篇：S03-J04 · 回溯与搜索。

1. 一句话结论

链表题只有四个动作：走、断、接、反转。所有题都是它们的组合——难点从来不是"逻辑"，是"指针改完丢了引用"。

动作	代码	风险
走	`p = p.next`	走过界（`null`）
断	`prev.next = null`	断早了丢后半段
接	`a.next = b`	接之前忘存 `b` 的原后继
反转	三指针 `prev/cur/next`	顺序写错就断链

两个保命习惯：

虚拟头节点（dummy）：所有"可能改头节点"的题都用它，最后返回 dummy.next。
改指针前先存后继：nxt = cur.next 永远写在 cur.next = prev 之前。

2. 实测：迭代 vs 递归

10 万个节点反转：

实现	结果
迭代	14.7 ms，无栈风险
递归	3,000 个节点就 `RecursionError`（Python 默认递归上限 1,000；Java 默认栈约 1 万层）

结论：链表题优先写迭代。递归写法更短，但栈深度 = 链表长度，长链表直接崩。

3. 四个基本动作的完整模板

3.1 反转整条链表（迭代）

ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode nxt = cur.next;   // ① 先存后继
        cur.next = prev;           // ② 反转
        prev = cur;                // ③ 前移
        cur = nxt;
    }
    return prev;                   // 新头
}

画图法：纸上画三个格子 prev | cur | nxt，每轮把 cur.next 指向 prev，然后整体右移一格。

3.2 合并两条有序链表

ListNode merge(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), t = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { t.next = a; a = a.next; }
        else                { t.next = b; b = b.next; }
        t = t.next;
    }
    t.next = (a != null) ? a : b;   // 剩下的一整段直接接上
    return dummy.next;
}

注意：剩下那段不需要逐个接，直接挂上即可（链表不是数组）。

3.3 快慢指针找中点 / 判环

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
// 奇数长度：slow 在正中；偶数长度：slow 在右中（取决于初始化）

判环：若 slow == fast 则有环；找环入口：相遇后一个指针回头，再同速走，相遇点即入口。

4. 代表题精讲

4.1 #24 两两交换（补写 `E-S03-114`）

ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0); dummy.next = head;
    ListNode prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode a = prev.next, b = a.next;
        a.next = b.next;      // a 指向 b 的后继
        b.next = a;           // b 指向 a
        prev.next = b;        // prev 接上 b
        prev = a;             // 前进两格
    }
    return dummy.next;
}

要点：prev 是"上一组的尾"，每轮改三个指针；边界由 while 条件保证（不足两个节点就停）。

4.2 #61 旋转链表（补写 `E-S03-115`）

题目：把链表每个节点右移 k 位（k 可能大于长度）。

ListNode rotateRight(ListNode head, int k) {
    if (head == null || head.next == null) return head;
    int n = 1; ListNode t = head;
    while (t.next != null) { t = t.next; n++; }   // 找尾，计数
    t.next = head;                                 // 连成环
    int step = n - k % n;                          // 新尾的位置
    while (step-- > 0) t = t.next;                  // 走 step 步
    ListNode newHead = t.next; t.next = null;       // 断开
    return newHead;
}

洞察：先成环再断，避免"从后往前"的麻烦；k % n 处理 k > n。

4.3 #82 删除重复元素 II（补写 `E-S03-116`）

题目：删除所有"有重复"的节点，只保留只出现一次的值。

ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0); dummy.next = head;
    ListNode prev = dummy, cur = head;
    while (cur != null) {
        if (cur.next != null && cur.val == cur.next.val) {
            int v = cur.val;
            while (cur != null && cur.val == v) cur = cur.next;  // 跳过整段
            prev.next = cur;                                    // prev 直接接上
        } else {
            prev = cur; cur = cur.next;
        }
    }
    return dummy.next;
}

与 #83 的区别：#83 保留一个（遇到重复时保留第一个），#82 整段删掉。

4.4 #23 合并 K 个有序链表

方案	复杂度	说明
逐个合并	O(N·k)	每次合并都要重走
两两分治	O(N log k)	归并思想
小顶堆	O(N log k)	每次取最小头，代码更直观

4.5 #25 K 个一组翻转

// 1) 先数够 k 个：不足则原样返回
// 2) 翻转这 k 个（子链表反转）
// 3) 递归/迭代处理下一组，接回

边界：k=1 直接返回；最后一组不足 k 个不翻。

4.6 #86 分隔链表

洞察：建两条子链（<x 与 ≥x），最后拼接，比"原地插入"简单得多，且稳定（保持相对顺序）。

5. 11 题模式对照

题	动作组合	关键点
2	走 + 进位	长度不等、最后进位
19	快慢指针	快指针先走 N 步；dummy 免特判
21	合并	剩余段整体接
23	分治/堆	O(N log k)
24	三指针换位	补写（E-114）
25	分段反转	先数够 k
61	成环 + 断开	补写（E-115）
82	跳过整段	补写（E-116）
83	跳过重复	保留一个
86	双链拆分	稳定且简单
92	四指针区间反转	dummy + 前驱

6. 五个误区

误区	真相
"递归反转更优雅"	栈深 = 链表长，长链表会崩（实测 3,000 就 RecursionError）
"改指针顺序无所谓"	先改后存后继 = 丢失剩余链表
"合并时要逐个接剩余节点"	直接挂整段
"dummy 只是好看"	它消除"头节点被删/被改"的全部特判
"#82 与 #83 一样"	一个整段删，一个保留一个

7. 自检

反转链表时，为什么 nxt = cur.next 必须写在 cur.next = prev 之前？
10 万节点反转，迭代与递归的结果差别是什么（实测）？
#61 为什么要先成环？
#82 与 #83 的删除策略差在哪？
dummy 节点在 #19/#24/#82/#92 中各解决了什么特判？

8. 下一篇

S03-J04 · 回溯与搜索：把"枚举"写成树

链表管"结构"，回溯管"枚举"。下一篇给出"选择 → 递归 → 撤销"三段式，以及去重与剪枝的判据（实测 N 皇后 n=8 只有 2,057 个搜索节点，暴力枚举是 8⁸ ≈ 1,677 万）。

本篇属于系列《S03 · 数据结构与算法》。旧文来源：11 张题解卡；补写 #24/#61/#82（E-S03-114~116）。迭代反转 100k = 14.7 ms、递归 3,000 即 RecursionError 为 2026-11-05 实测。