虚拟头结点：链表操作的万能哨兵

链表题里有一半以上的bug，都出在"头结点要特殊处理"这件事上。这一篇介绍一个一劳永逸的技巧：虚拟头结点（dummy head）。它不存任何业务数据，只是站在真正的头结点前面，把所有操作变成同一种逻辑。

一、为什么删除头结点是特例

先看没有 dummy 时的删除逻辑。要删除链表中值为 val 的节点，需要找到它的前一个节点，然后让前一个节点"跳过"它：

// 删除中间节点 cur：拿到前驱 prev 后
prev.next = cur.next;

问题在于：头结点没有前驱。它的"前一个节点"是 head 引用本身，删除头结点意味着要改变传入的引用指向：

if (head.val == val) {
    head = head.next; // 删除头结点：head 引用后移
}

于是不加 dummy 的写法需要一个 if 分支专门处理头结点，甚至要写 while 循环连续删除多个头结点。逻辑被劈成了两半，出错概率直线上升。

二、dummy 如何统一逻辑

虚拟头结点的做法是：new 一个不存值的节点放在最前面，让原头结点"降级"为普通节点。

原始链表:            head -> [1] -> [2] -> [3]
加了 dummy 之后: dummy -> [1] -> [2] -> [3]
                            ^ 真正的头结点，但只是个普通节点了

现在无论删除哪个节点，它的前驱一定存在：

删除节点 1？前驱是 dummy。
删除节点 2？前驱是节点 1。

删除逻辑从此只有一条路，头结点特例彻底消失。返回时也不再返回 head，而是返回 dummy.next——因为真正的头结点可能已经被删掉了。

三、实战一：移除链表元素（LeetCode 203）

题目：删除链表中所有值等于 val 的节点。有了 dummy，代码非常干净：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 虚拟头结点，指向真正的头
        ListNode dummy = new ListNode(-1, head);
        ListNode cur = dummy; // cur 站在"待检查节点"的前一个位置
 
        while (cur.next != null) {
            if (cur.next.val == val) {
                // 跳过目标节点，相当于删除
                cur.next = cur.next.next;
                // 注意：这里 cur 不动，因为新的 cur.next 还没检查
            } else {
                cur = cur.next;
            }
        }
        return dummy.next; // 新的头结点
    }
}

两个关键细节：

cur 始终停在前驱上。删除操作改的是 cur.next，删完之后新的 cur.next 是一个"没检查过"的节点，所以 cur 不能前进，下一轮循环再判断。
返回 dummy.next 而不是 head。如果所有节点都被删光，dummy.next 是 null，而原来的 head 还指着已被逻辑删除的节点。

四、实战二：设计链表（LeetCode 707）

707 是 dummy 技巧的集中演练：实现 MyLinkedList 类，支持按下标增删查。这道题的真正考点是 index 的边界约定：

get(index)：index 从 0 开始，从头结点数起；
addAtHead/addAtTail/addAtIndex(index, val)：addAtIndex 中 index 等于链表长度时追加到尾部，大于长度则什么都不做；
deleteAtIndex(index)：仅当 0 <= index < length 才删除。

写这类题的方法论是：先明确每个指针"数到第几个"的语义，再动手。这里统一约定——dummy 是第 0 个位置，getPre(index) 返回第 index 个节点的前驱：

class MyLinkedList {
    ListNode dummy; // 虚拟头结点
    int length;
 
    public MyLinkedList() {
        dummy = new ListNode(-1);
        length = 0;
    }
 
    // 返回第 index 个节点的前驱（dummy 视为第 0 个位置的节点）
    // 所以 getPre(0) 永远返回 dummy，保证后面增删不用判空
    private ListNode getPre(int index) {
        ListNode cur = dummy;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }
 
    public int get(int index) {
        if (index < 0 || index >= length) return -1;
        return getPre(index).next.val;
    }
 
    public void addAtHead(int val) { addAtIndex(0, val); }
 
    public void addAtTail(int val) { addAtIndex(length, val); }
 
    public void addAtIndex(int index, int val) {
        if (index > length) return; // 越界直接放弃
        if (index < 0) index = 0;
        ListNode pre = getPre(index);
        ListNode node = new ListNode(val);
        node.next = pre.next; // 先接后断，顺序不能反
        pre.next = node;
        length++;
    }
 
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= length) return;
        ListNode pre = getPre(index);
        pre.next = pre.next.next;
        length--;
    }
}

注意 addAtIndex 里"先接后断"：node.next = pre.next 必须在 pre.next = node 之前。反过来写，后半段链表的入口就丢了。其实有了 pre.next 这个表达式，后半段随时可以重新找到，但养成"先保存再覆盖"的习惯能避免绝大多数事故。

增删查都委托给统一的 getPre，头插（index=0）、尾插（index=length）、中间插走的是同一套代码——这正是 dummy 的价值：边界不再是分支，而只是参数。

五、什么时候不需要 dummy

dummy 不是万能钥匙，以下场景它帮不上忙：

纯遍历读值：只是从头到尾走一遍（比如求长度、找某个值），head 引用不动，不涉及增删，不需要 dummy。
反转链表：206 的迭代反转从头开始逐个改方向，过程中 head 的指向变化本身就是算法的一部分，加 dummy 反而绕（但 24 两两交换、25 K 个一组这类"分组操作"仍然离不开 dummy）。
快慢指针判环：141/142 只在环里转，没有删除插入操作，dummy 无用武之地。
题目已给出尾节点或前驱：比如"删除给定节点（只给该节点）"这类题，操作对象直接在手，不需要从头找前驱。

一句话总结：只要涉及"在头结点处增删"或者"统一处理位置未知的增删"，就用 dummy；只读不写，就不用。

六、常见错误清单

dummy 声明了忘记 new：ListNode dummy; 之后直接 dummy.next = head 会抛 NullPointerException。正确写法 ListNode dummy = new ListNode(-1, head);。
返回了 head 而不是 dummy.next：头结点被删的场景直接错。写完先问自己"真正的头可能变吗"。
删除后忘了 cur 的去留：删除分支里 cur 前进，会跳过连续两个待删节点（如 1 -> 1 连续相同值）。
修改 next 前没保存后继：典型如反转中先写 cur.next = prev，再想找原来的后继已经找不到了。
index 语义前后不一致：get 按头结点数起、add 按虚节点数起，实现到一半发现对不上。先在纸上统一口径再写码。

参考

代码随想录 · 链表专题