链表操作核心技巧：虚拟头节点与双指针实战解析

开始前的几句话

代码随想录训练营day4，按进度正好是链表部分的核心攻坚日。今天这三道题——移除链表元素、设计链表、反转链表——属于典型的“一看就会、一写就废”的题型。我见过太多人卡在这一天，不是不会思路，是边界条件一错再错，while循环一不小心就写成了死循环。这篇东西把我自己当年踩过的坑、总结出来的套路全部摊开讲，帮你把链表这块的底层手感彻底练出来。

适合谁看？正在跟代码随想录训练营刷题的人、准备面试但链表基础不牢的人、以及所有被指针操作折磨过的编程学习者。不管你是第一遍刷还是二刷巩固，这篇都能让你少走不少弯路。

1. 训练营day4的定位：为什么链表是面试的分水岭

1.1 从数组到链表的思维切换

很多人在day1到day3还在用数组的思维做题，到了day4链表这里突然就懵了。原因很简单：数组的一切操作都是基于“连续内存+下标访问”，你想处理哪个元素，直接 nums[i] 招呼过去就行；链表则完全反过来，每个节点只知道自己和下一个节点的位置，你要找一个节点，没有任何捷径，只能从头节点一个next一个next地走过去。

这个思维切换，本质上是把习惯的“静态视图”换成“动态视图”。数组操作好比在停车场的固定车位上找车，车位有编号，报号就能到；链表操作则像跟着一条写满线索的纸条找人，纸上写着“下一个人在东街拐角”，你走到东街拐角再看下一张纸条。纸条可能断，可能指错，还可能绕回原地，这就是为什么要专门拿出一天来练链表。

代码随想录训练营day4安排的这三道题，不是随便挑的。移除链表元素练的是“我怎么安全地跳过不要的节点”，设计链表练的是“我怎么把一个链表的增删改查全部写对”，反转链表练的是“我怎么把每个指针的方向都掰过来”。三题层层递进，把链表操作里最容易错的三个环节挨个练了一遍。

1.2 三道题目掩盖了一个共同核心：虚拟头节点

先说一个很多人没意识到的点：这三道题，包括训练营后面大量链表题，核心解法全都绕不开“虚拟头节点”（dummy node）这个技巧。我甚至可以说，谁掌握了dummy node，谁就掌握了链表题的半边天。

为什么需要虚拟头节点？因为头节点没有前驱。你删除一个普通节点，需要让它的前驱指向它的后继；但删除头节点，你连前驱都找不到，只能单独写一套逻辑。这就是万恶的“头节点特殊处理”。而虚拟头节点的思路，就是在真正的头节点前面再缝上一个假的节点，让所有节点包括原本的头节点在内，都有了统一的前驱。从此之后，你再也不用为了“万一删除的是头节点”这种情况写if判断了，所有操作一视同仁，代码直接清爽一大截。

后面做设计链表、反转链表的时候你会发现，这个技巧反复出现，而且每次形态还略有不同——有时是 ListNode* dummy = new ListNode(0, head)，有时是 ListNode* dummy = new ListNode(); dummy->next = head;——但它背后的哲学是同一个：给边界条件一个统一的出口。

2. 题一：移除链表元素，边界条件最容易翻车的地方

2.1 题目到底在考什么

题目内容不复杂：给一个链表头节点和一个值 val，让你把所有节点值等于 val 的节点全部删掉。比如链表 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6，删掉所有值为6的节点，得到 1 -> 2 -> 3 -> 4 -> 5。

看着简单对吧？但考试和面试里这道题的通过率从来都不高。根子上的原因是：删除节点这个动作本身不难，但“我怎么知道当前节点是安全的可以访问的”以及“删除之后前驱和后继的指针怎么接续”这两件事，新手经常剪不断理还乱。

我们来拆解一下删除一个中间节点的完整步骤。假设链表长这样：prev -> cur -> next，现在要删掉 cur。你需要做的就是把 prev->next 指向 next，然后释放掉 cur 的内存。这一步本身很简单，但问题来了——如果 cur 恰好是头节点呢？prev 是谁？不存在。所以你不得不为头节点单独写分支，代码丑不说，还特别容易漏。

2.2 核心解法：用虚拟头节点统一逻辑

解决思路就是用虚拟头节点。我们来看代码：

cpp复制ListNode* removeElements(ListNode* head, int val) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* cur = dummy;
    while (cur->next != NULL) {
        if (cur->next->val == val) {
            ListNode* tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        } else {
            cur = cur->next;
        }
    }
    return dummy->next;
}

这个代码的精髓就是 while (cur->next != NULL) 这个条件。为什么不是 while (cur != NULL)？因为我们要统一检查“下一个节点该不该删”，而不是“当前节点该不该删”。这样当删除动作发生时，cur本身的位置没变，只是它的next指针变了，循环逻辑不会乱。

我自己第一次写的时候，喜欢写成：

cpp复制while (cur != NULL) {
    if (cur->val == val) { ... }
}

这种写法的问题是：删除当前节点后，你需要一个prev来接线，于是代码瞬间多出两个指针要维护，而且删除头节点的时候还得单独处理。用虚拟头节点结合“看下一个节点”的思路，整个逻辑就变成了一种统一的模式，基本不会出边界错误。

2.3 两个细节坑位，都是过来人的血泪

第一个坑是返回值。这里特别提醒：return dummy->next。很多人最后 return head，问题是head可能已经被删了，你return的正好是一个悬空指针。注意看我们的代码，如果链表头节点的值就是val，那删除后原head节点已经被delete了，你return head直接出大事。

第二个坑是内存释放。力扣的题你写C++不释放内存可能也能过，但面试的时候面试官是会盯着看的。删除节点以后，要把被删节点指针存下来，然后delete掉。养成这个习惯，否则代码review的时候一定会被cue。我在代码里专门写了一句 ListNode* tmp = cur->next; 就是为了一边改指针一边留后路，这个细节后面写设计链表也一样要用。

注意：while循环里删完节点之后，cur不要动。只有当前节点不需要删除时，cur才往前走。我见过很多人看代码觉得“删除后cur应该指向被删节点的下一个”，其实不对，因为在删除动作里，cur->next已经被更新了，cur自己不需要移动，移动反而会跳节点。

3. 题二：设计链表，工程能力的试金石

3.1 为什么这道题和前面那道不在一个量级

移除链表元素只是操作一个现成的链表，而设计链表这道题要求你实现一个完整的链表类，get(index)、addAtHead、addAtTail、addAtIndex、deleteAtIndex 五个方法一个不少。这道题对很多人来说是从“会做题”到“会写代码”的转折点，因为它不仅考察单点操作，更考察你在一个完整类结构里统一管理增删改查的能力。

代码随想录训练营把这道题压在day4，我觉得是有深意的：前面那道题练的是“你会不会删”，这道题练的是“你会不会在一个工程规模下有条理地删和增”。

3.2 同样是虚拟头节点，但玩法不一样

这道题里我依然用虚拟头节点，但每一个方法都要用它。get 的时候从dummy.next开始找，addAtHead 的时候把新节点插到dummy之后，deleteAtIndex 的时候同样用“看下一个”的模式。

写出来大概是这样的骨架：

cpp复制class MyLinkedList {
public:
    struct LinkedNode {
        int val;
        LinkedNode* next;
        LinkedNode(int val) : val(val), next(nullptr) {}
    };

    MyLinkedList() {
        dummyHead = new LinkedNode(0);
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= size) return -1;
        LinkedNode* cur = dummyHead->next;
        while (index--) {
            cur = cur->next;
        }
        return cur->val;
    }

    void addAtHead(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        newNode->next = dummyHead->next;
        dummyHead->next = newNode;
        size++;
    }

    void addAtTail(int val) {
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyHead;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = newNode;
        size++;
    }

    void addAtIndex(int index, int val) {
        if (index > size) return;
        if (index < 0) index = 0;
        LinkedNode* newNode = new LinkedNode(val);
        LinkedNode* cur = dummyHead;
        while (index--) {
            cur = cur->next;
        }
        newNode->next = cur->next;
        cur->next = newNode;
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        LinkedNode* cur = dummyHead;
        while (index--) {
            cur = cur->next;
        }
        LinkedNode* tmp = cur->next;
        cur->next = cur->next->next;
        delete tmp;
        size--;
    }

private:
    LinkedNode* dummyHead;
    int size;
};

注意这个类里我多维护了一个 size 变量。这个东西太重要了，get 和 deleteAtIndex 的越界检查都靠它。没有 size，你每次都要遍历到index位置才能知道到底有没有越界，最后判断的是“走到头了没走到index”，代码又麻烦又容易错。用一个size字段记录节点总数，所有越界判断都变成一次整数比较，这个工程习惯值得你在所有链表设计里保留。

3.3 addAtIndex是五兄弟里最心机的

如果你自己写一遍这个题，你会发现 addAtIndex(index, val) 才是真正的重点题型。这个方法的逻辑是：在第index个节点之前插入一个新节点，链表长度加一。看似只是addAtHead和addAtTail的推广，但边界条件相当刁钻。

先看第一个易错点：index > size 时不插入，但 index == size 时是允许的——因为第size个位置就是链表末尾，在末尾前插入等于尾插。很多人会写成 index >= size 直接return，把尾插给屏蔽掉了，后面的测试用例立刻翻车。

再看第二个易错点：index < 0 时应该插到头部。题目描述里说了index为0或者负数都算插入头部，所以必须有一个 if (index < 0) index = 0; 的修正。不做这个处理，while循环里 index-- 如果是负数，循环根本不会执行，新节点会插到dummy后面还是头节点后面，逻辑倒是碰巧对，但代码的语义就歪了。

第三个易错点其实是“插入后谁指向谁”的顺序问题。正确的顺序是：先让新节点指向后面的节点，再让前面的节点指向新节点。顺序反了会怎样？如果你先让 cur->next = newNode，那么原来 cur->next 指向的链表后半段就丢失了，你再也找不到它，新节点只身挂上去，后面一整截都不见了。这个顺序问题几乎每个初学者都会踩一次，我建议你直接在代码旁边用笔画一下两个箭头改动的先后顺序，画一次就再也不会错了。

4. 题三：反转链表，双指针思维的第一个正式训练场

4.1 从故事讲起：为什么反转链表难倒一片人

反转链表题目很朴素：把一个链表完全反过来。1 -> 2 -> 3 -> 4 -> 5 变成 5 -> 4 -> 3 -> 2 -> 1。看起来就只是把箭头方向全部调转，但大部分人第一次写都会卡住，原因很微妙——你平时遍历链表是“从前往后”的，反转却要求你“让每个节点回过头来指向前一个节点”，这等于一边往前走，一边修理刚走过的路。你的脑子还没接受“前一个节点现在要变成后一个节点的next”这种时空错乱的感觉。

我自己的体会是，这题的坎不在于代码而在于图像思维。你必须在脑海里把链表画成“一串箭头”，然后想象有两个指针，一前一后，前指针负责“指路”，后指针负责“接线”，两个指针同步往前走，每走一步就把路过的指针方向掰过来。

4.2 双指针写法：最容易被忽略的保存动作

先上代码，双指针解法是训练营推荐的主解，也是理解递归解法的基础：

cpp复制ListNode* reverseList(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    while (cur != nullptr) {
        ListNode* next = cur->next;   // 先保存下一个节点
        cur->next = prev;             // 掰指针方向
        prev = cur;                   // 后指针跟上
        cur = next;                   // 前指针继续往前走
    }
    return prev;
}

这个代码只有四行核心逻辑，但顺序错一点都不行。我先说保存那一行的重要性。你没保存 cur->next，就直接执行 cur->next = prev，此时当前节点原本指向的下一个节点就找不到了，整个链表的后半段直接失联，后面还怎么遍历？所以那个 ListNode* next = cur->next 必须出现在翻转之前。

再说返回值的坑。很多人最后 return cur，认为cur走到最后就是新头节点。但你看这个循环的退出条件，退出时cur已经是nullptr了，真正的最后一个节点已经被prev握着。所以必须 return prev。这个点几乎每次都有人错，我还在评论区看过“为什么return head不对”，因为head现在已经被翻到链表的最后面了，它再也不是头了。

迭代写法的本质是：维护prev和cur两个指针，让链表的next指针逐个掉头。每经过一个节点，这个节点的next就被永久改写，改完之后prev跟上，cur继续前进。这个过程很像两列火车在同一条轨道上错车，一列先停，另一列先走，交替前进。

4.3 递归写法：另一种视角，面试加分项

双指针写法写明白之后，可以试试递归。递归写法更短，但理解门槛更高：

cpp复制ListNode* reverseList(ListNode* head) {
    if (head == nullptr || head->next == nullptr) return head;
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

这个递归的关键理解点在于：reverseList(head->next) 这个调用返回的是“从head->next开始，整个后半段被反转后的新头节点”。调用完这行，后半段的链表已经全部掉头了，唯一没接上的就是原来的头节点head。此时原来的head->next（即现在的后半段尾部）还依然指向head吗？注意，反转之后的链表里，head->next这个节点已经变成了整个后半段的尾节点，它的next此时指向nullptr。

那我们要做的只有两件事：第一，让head->next->next重新指向head，把head接到反转后的链表末尾；第二，让head->next指向nullptr，防止它残留原来的引用，否则会出现环。最后返回newHead。

递归这个东西，如果一下子看不懂就不用强求，可以先把双指针写法写到滚瓜烂熟，等链表题目刷多了再回来体会递归。面试时两种解法都能讲清楚绝对是加分项，因为这说明你不是在背题，是真的理解链表的指针操作逻辑。

5. 实操演练：三个题的完整破题过程

5.1 从零开始的一个完整案例

为了把上面三题串起来，我们拿一个具体链表走一遍完整的操作过程。假设初始链表为 1 -> 2 -> 6 -> 3 -> 4 -> 5 -> 6，要求移除所有值为6的节点。

第一步，建立虚拟头节点dummy(0)，dummy->next指向原来的head(1)。然后cur从dummy出发，检查cur->next的值。

• cur在dummy，cur->next是1，不是6，cur后移。
• cur在1，cur->next是2，不是6，cur后移。
• cur在2，cur->next是6，命中，tmp指向6，然后2的next指向3，删除6。cur不动。
• cur仍在2，cur->next是3，不是6，cur后移。
• cur在3，cur->next是4，不是6，cur后移。
• cur在4，cur->next是5，不是6，cur后移。
• cur在5，cur->next是6，命中，tmp指向6，然后5的next指向nullptr（因为原链表最后节点就是6，6的next本来就是nullptr），删除6。cur不动。
• cur仍在5，cur->next是nullptr，循环退出。

最终dummy->next是1，链表为 1 -> 2 -> 3 -> 4 -> 5。整个过程看起来简单，但你注意，整个过程中cur位置变化非常规整：要么原地等，要么后移一步，从来不需要回头，也不需要额外记录前驱。这就是虚拟头节点+看下一个模式的精髓：代码写出来之后，可推理性和可调试性极高。

5.2 用设计链表的五个接口做一轮增删改查

现在假设我们新建一个空的MyLinkedList，然后依次执行以下操作，体验五个接口配合的过程。

1. addAtHead(1)：链表 1
2. addAtTail(3)：链表 1 -> 3
3. addAtIndex(1, 2)：链表 1 -> 2 -> 3
4. get(1)：返回2
5. deleteAtIndex(1)：链表 1 -> 3
6. get(1)：返回3

全程下来你会发现，每一部操作的关键都在于先在纸上标好size的变化。addAtIndex(1, 2) 执行前size是2，插入后size变3；deleteAtIndex(1) 执行前size是3，删除后size变2。所有接口的边界判断都基于size，而size的增减和接口行为必须完全同步，哪怕你漏了一个size--，后面的get操作就会因为边界判断错误而越界。我在实际debug这类题目时候的检查顺序就是：先查size，再看指针，最后看值，几乎是百试百灵。

5.3 反转链表时的大脑模拟

以 1 -> 2 -> 3 为例走一遍双指针反转。

• 初始：prev=nullptr，cur=1。
• 第一轮：保存next=2；1的next指向nullptr；prev=1；cur=2。
• 第二轮：保存next=3；2的next指向1；prev=2；cur=3。
• 第三轮：保存next=nullptr；3的next指向2；prev=3；cur=nullptr。
• 循环退出，return prev，即3。

此时链表为 3 -> 2 -> 1。你可以用这个例子推演递归版本：reverseList(1)里调用reverseList(2)，reverseList(2)里调用reverseList(3)，3的next是nullptr直接返回3；回到2那一层，head是2，head->next是3，执行3->next=2，2->next=nullptr，返回3；回到1那一层，head是1，head->next是2（注意此时2的next已经是nullptr了，但我们存了2这个节点引用），执行2->next=1，1->next=nullptr，返回3。层层递归像一个卷起来的弹簧，从最里面一层开始往回拨指针，最终整个链表反转完成。

6. 链表刷题的高频翻车现场与排查方案

6.1 空指针访问：谁是元凶

链表题里最常见的runtime error就是空指针访问。典型场景是：你删除了某个节点，但后续还有操作试图访问这个节点的next，或者你在反转时没保存next就掰了指针，导致cur变成野指针。

我总结的排查口诀叫“三查”：循环条件查了吗？进入循环时当前节点可能为空吗？访问cur->next前确认cur不为空了吗？每次你写下 cur->next 前面都要有意识地对自己提出这三个问题。你要是能在刷题阶段养成这种习惯，面试手写链表时基本不会再因为空指针被人叫停。

6.2 死循环：为什么你的程序不会结束

死循环的根源多半是链表中出现了环。反转链表时要是忘了把head->next置为nullptr，或者设计链表addAtIndex时先让cur->next指向新节点，新节点的next指向自己，都会成环。

排查死循环的有效手段是：在一段循环里放一个计数器，最多跑链表长度+10次就跳出，打印当前节点的值。一旦发现节点值重复出现，就能定位到环的位置。这个方法虽然粗暴，但在本地调试时非常高效。我自己在练习阶段经常用这招。

另外还有一个比较隐蔽的死循环来源：删除节点时cur没有移动。我们前面讲移除链表元素时说了“删除后cur不动”，那是正确写法。但如果你在删除节点后把一个正常的“未命中移动”也省略了，就可能在出现连续需要处理的节点时，其中某个位置永远不会走到，导致无限循环。区分“删除后不动”和“无论如何都不动”，是边界调试里最容易混淆的点。

6.3 内存问题排查：C++写链表绕不开的坎

C++写链表题会遇到内存泄漏和悬空指针的问题。内存泄漏的典型原因是删除了节点但没有delete，或删除了指针但别的指针还指向这块内存。悬空指针则是你delete了节点，但另一个指针仍然保存着它的地址，再次访问时行为就是未定义的。

我的做法是：每个delete之后立刻把指针置为nullptr或不再使用；每次new之后，检查是否需要在析构函数里统一释放。力扣的判题环境可能不会因为内存泄漏报错，但面试中这是考察点。用Java或Python刷题的人没有这个烦恼，但C++选手必须把这个写进肌肉记忆。

6.4 常见问题速查表

7. 关于链表操作的一些个人心得

刷题阶段我最大的体会是：链表题的核心不在技巧，而在“每一步都清楚自己在改哪个指针”。很多人写代码快，但问一句“此时谁的next指向谁”就卡壳。应对办法其实很简单，凡是卡住就在草稿纸上画三个节点，把指针标出来，一遍一遍手动跑代码。这个过程看似笨拙，但对建立指针感极其有效。

另一个体会是：虚拟头节点不是一种取巧的hack，而是工程实践中真实常用的技巧。很多工业级链表实现都会用一个sentinel节点来统一空表和非空表的操作逻辑，这跟刷题时用dummy node是同一个思路。所以你在训练营day4学到的不是三道孤立的题目，而是一套可以迁移到后续无数链表题里的通用思维框架。day4之后还有更多链表题等着你，但只要你掌握了“虚拟头节点统一边界”“改变指针前先保存后继”“返回前想清楚新头是谁”这三条主线，后续的链表题难度直接下降一半。

最后分享一个我自己刷链表题的独门习惯：每道题写完之后，把代码拿到本地用几个预设的边界用例跑一遍。比如空链表、只有一个节点、删除头节点、插入到尾节点、连续相同值的节点。这些边界用例往往比题目自带的用例更考验实现质量，也最能暴露问题。坚持这么做，你的链表手感会提升得比想象中快得多。