企业官网建设流程全解析

训练营第三天，题目一列出来我就知道今天是链表专场：第203题移除链表元素、第707题设计链表、第206题反转链表。这三道题我前后刷过好几遍，但每次重新做还是会有新的体会，尤其是虚拟头节点这个东西，一旦用熟了，再看链表题整个思路都会顺很多。这篇文章就把这三题完整拆一遍：每题的思考过程、最终可用的代码、容易掉进去的坑，以及刷完三题之后沉淀下来的一套链表题通用处理方式。如果你刚开始刷链表，或者正在跟训练营的打卡，这份整理可以直接当参考。

1. 为什么第三天要集中刷链表题

1.1 数组和链表：两种完全不同的存储思路

前两天的题目基本以数组为主，二分查找、双指针、滑动窗口，全部都是基于“连续内存、下标访问”这套模型。数组的优势是从头到尾太直观了，一个循环加一个下标，想访问哪个位置就访问哪个位置。链表恰恰相反，节点在内存里是东一个西一个的，唯一的联系就是每个节点里那个next指针。

这种差异带来的第一个冲击是：很多以前不需要考虑的东西，在链表里突然变成核心矛盾了。比如“找到第index个节点”，数组是arr[index]，一步到位；链表得从头节点开始，一格一格顺着指针走，还要自己判断走几步、走到哪里该停。再比如“删除第index个节点”，数组是往后移动元素，链表得先找到前一个节点，再把它指向下下个节点，而这个“前一个节点”恰恰是链表操作里最容易搞错的地方。

代码随想录训练营把链表安排在第三天，我觉得是有讲究的。前面两天用数组把循环、边界、指针这些基本功练过一遍，第三天再上链表，重点就不是“你怎么遍历”，而是“你怎么操作节点之间的引用关系”。这个转变是必须发生的，因为链表的题目几乎每一道都在考“谁指向谁”，稍不留神就把指针指丢了。

1.2 三道题把链表的基础操作全涵盖

这三题不是随便选的，覆盖了链表最基本的几类操作：

第203题是删除。删除是所有链表操作里最常考的，而它的核心难点是头节点没有前驱，删除头节点和删除中间节点的处理方式不一样，要用虚拟头节点把逻辑统一。

第707题是设计。它要求你原封不动实现一个单链表的增删改查接口，相当于把链表底层全部手写一遍。写完这一题，链表的内存结构、索引偏移、边界判断基本就刻进脑子里了。

第206题是反转。反转看起来是“改指针方向”，实际上考的是在遍历过程中如何保住下一个节点的指针，不至于因为改了当前节点的next就断了后路。

三题分别对应“会删”“会建”“会反转”，这个组合做完，后面再遇到环形链表、两两交换节点、删除倒数第n个节点这些进阶题，基础就扎实了。

2. 第203题：移除链表元素，先练会“删除一个节点”

2.1 两个思路：先处理头部 vs 虚拟头节点

题目的描述很简单：给你一个链表的头节点head和一个整数val，删掉链表里所有值等于val的节点。比如链表是1->2->6->3->4->5->6，val是6，最终应该返回1->2->3->4->5。

删除一个普通节点的操作本身不难，核心就一句话：让当前节点的next跳过要删的那个节点。

cur->next = cur->next->next;

难就难在头节点。如果头节点本身就等于val，它没有前驱节点可以来执行“跳过”这个动作，你只能直接把head往后移动一位。这就要单独写一段逻辑，处理完头部所有等于val的节点之后，再处理剩下的。

不处理头节点时的代码是这样：

ListNode* removeElements(ListNode* head, int val) { while (head != nullptr && head->val == val) { ListNode* toDelete = head; head = head->next; delete toDelete; } if (head == nullptr) return head; ListNode* cur = head; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* toDelete = cur->next; cur->next = cur->next->next; delete toDelete; } else { cur = cur->next; } } return head; }

注意这段代码里有两个细节。第一个是删除节点后cur不能立刻往右移动，因为移动之后新的cur->next可能仍然等于val，比如链表里连续出现两个6，删除第一个6之后，cur的next正好还是6，如果这时候cur = cur->next，就会漏删。第二个细节是C++里new出来的节点删除后要手动delete，虽然在线判题不析构链表也能过，但在本地练习时不delete会内存泄漏。

2.2 虚拟头节点让代码变得对称

上面的解法问题在于，为了让删除逻辑统一，我不得不先用一个while循环把头部值等于val的节点全部处理掉，然后再进入后面的循环。这个“先处理头部”的步骤很容易漏，尤其是当val出现在连续多个头节点的时候。

其实这个问题有一个更优雅的解法：自己造一个虚拟头节点，让它指向原链表的head。这样一来，原来的头节点也变成“有前驱”了，删除头节点和删除中间节点的代码就可以完全一致。

ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); dummyHead->next = head; ListNode* cur = dummyHead; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* toDelete = cur->next; cur->next = cur->next->next; delete toDelete; } else { cur = cur->next; } } ListNode* resultHead = dummyHead->next; delete dummyHead; return resultHead; }

对比两个版本就会发现，虚拟头节点的核心价值不是提高时间效率，而是让代码的每个分支都变得简单。没有虚拟头节点时，“处理头节点”“处理中间节点”是两套逻辑；有了虚拟头节点之后，所有节点一视同仁，只需要一套逻辑走到底。这是我在刷链表题时最常用的一种简化手段，后面第707题设计链表时也离不开它。

2.3 第203题的时间复杂度和细节

这个解法的时间复杂度是O(n)，因为整个链表只遍历了一遍；空间复杂度是O(1)，除了新建的那个dummy节点，没有额外数据结构。

我写这题容易犯的错是遍历条件写成while (cur != nullptr)，然后判断cur->next->val，这种情况在最后一个节点会直接空指针错误。正确写法是while (cur->next != nullptr)，因为cur是需要检查的前驱，cur->next才是待删节点。另一个容易出错的地方是delete顺序，一定先把toDelete保存下来，再改cur->next，最后再delete，顺序反了的话，被删节点的指针就找不到了。

提示：第203题是链表入门第一题，建议两种写法都亲手敲一遍。先写不带虚拟头节点的版本，体会一下处理头节点的麻烦，再写带虚拟头节点的版本，感受一下逻辑统一带来的清爽。这个过程比直接看答案有用得多。

3. 第707题：设计链表，把增删改查一次打通

3.1 设计一个带虚拟头节点的单链表

第707题的题干很长，要求自己实现一个链表类，支持获取第index个节点、头部插入、尾部插入、指定位置插入、指定位置删除这几个方法。很多第一次遇到这题的人会有点懵：链表本身的结构不是已经定好了吗，怎么还要自己实现一个？

实际上这题考的是你能不能从头到尾把一个完整的数据结构写出来，包括节点的定义、类成员的设计、每个方法的边界判断。我的做法是内部维护两个东西：一个虚拟头节点dummyHead，一个记录节点数量的整型size。

class MyLinkedList { private: struct ListNode { int val; ListNode* next; ListNode(int v) : val(v), next(nullptr) {} }; ListNode* dummyHead; int size; public: MyLinkedList() { dummyHead = new ListNode(0); size = 0; } };

为什么一定要虚拟头节点？因为在空链表上执行addAtHead、addAtTail、deleteAtIndex这些操作时，真实的头节点会不断变化。如果没有dummyHead，每次都要判断“链表是不是空的”“要删的是不是头节点”，代码会写出一堆分支。而有了dummyHead之后，dummyHead永远固定在链表最前面不参与业务，所有操作都从dummyHead开始走，空链表和非空链表就没有区别了。

3.2 索引偏移关系是突破口

这道题最容易翻车的地方在索引偏移。下标从0开始，这是常识，但和dummyHead放在一起时，就产生了一个“一步之差”的问题。

获取第index个节点时，目标本身就是节点，所以要从第一个真实节点开始走index步。第一个真实节点是dummyHead->next，所以：

ListNode* cur = dummyHead->next; while (index--) { cur = cur->next; }

插入和删除时情况不一样。要在第index个节点之前插入，或者删除第index个节点，真正需要移动的其实是它的前驱节点。前驱从谁开始找？从dummyHead开始。因为dummyHead是第0个真实节点的前驱，dummyHead之后走index步，恰好走到第index个节点之前。

这个过程可以用一个生活类比来理解：在一条队伍里找人。如果你要找“第六个人是谁”，你从第一个真实成员开始数六下。但如果你要“往第六个人前面插一个新人”，你必须先找到第五个人，因为新人要排在他后面。dummyHead扮演的是“排在所有真实成员前面的一个虚位”，从虚位开始走六下，正好落在第六个人前面。

3.3 五个方法逐个实现

完整的实现如下：

int get(int index) { if (index < 0 || index >= size) return -1; ListNode* cur = dummyHead->next; while (index--) { cur = cur->next; } return cur->val; } void addAtHead(int val) { ListNode* node = new ListNode(val); node->next = dummyHead->next; dummyHead->next = node; size++; } void addAtTail(int val) { ListNode* cur = dummyHead; while (cur->next != nullptr) { cur = cur->next; } cur->next = new ListNode(val); size++; } void addAtIndex(int index, int val) { if (index < 0) index = 0; if (index > size) return; ListNode* cur = dummyHead; while (index--) { cur = cur->next; } ListNode* node = new ListNode(val); node->next = cur->next; cur->next = node; size++; } void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode* cur = dummyHead; while (index--) { cur = cur->next; } ListNode* toDelete = cur->next; cur->next = cur->next->next; delete toDelete; size--; }

逐个解释一下关键点。

get的判断条件是index < 0 || index >= size，index等于size时已经越界，因为真实节点下标范围是0到size-1。

addAtHead是最简单的，新节点插到dummyHead后面，先让新节点指向旧第一个节点，再让dummyHead指向新节点。这里顺序不能反，如果先把dummyHead->next指给新节点，旧第一个节点就丢了。

addAtTail从dummyHead开始找尾巴，注意是while (cur->next != nullptr)，不是while (cur != nullptr)。因为我们要的是最后一个节点，而不是最后一个节点后面的空位，cur停在最后一个非空节点上，再把新节点挂上去。

addAtIndex有一个语义判断很关键：题干要求index等于链表长度时，新节点要追加到尾部。所以index == size是允许的，只有当index > size时才直接返回。index小于0时按头部插入处理，这一步等于把index改成0。

deleteAtIndex最容易被忽略的地方是判断越界。删除时index不能等于size，因为size下标对应的节点根本不存在。

3.4 边界条件对照表

刷这题时，我给自己整理了一张边界表，每次实现完都对着跑一遍：

这些边界条件在刷题时不是靠背的，而是靠“把特殊情况走一遍”推出来的。我强烈建议你拿到题目后先自己在纸上列出这个表，再开始写代码，这样写起来会非常有底气。

3.5 复杂度与扩展空间

这题代码写完后，复杂度也要能说清楚。get、addAtIndex、deleteAtIndex最坏都是O(n)，因为要顺着链表走到目标位置。addAtHead是O(1)，因为不涉及查找。addAtTail没有尾指针时是O(n)，如果额外维护一个tail指针可以降到O(1)，但tail指针在删除尾节点时也要同步更新，复杂度高了不少。

我见过有人一上来就写双链表加尾指针，结果addAtIndex和deleteAtIndex里对前后指针的维护频频出错。个人建议第一次刷还是用单链表加虚拟头节点，先把索引偏移和边界判断练透。这题本来就是考基本功的，不是考谁的数据结构更花哨。

提示：第707题的测试代码是一个可以直接抄作业的验证方式。在本地写一个main函数，依次调用addAtHead、addAtTail、addAtIndex、get、deleteAtIndex，每个操作后print整条链表，肉眼核对链路状态，比直接提交判题更快发现问题。

4. 第206题：反转链表，指针操作的经典

4.1 迭代法：三根指针往前走

第206题的要求是反转一个单链表，比如1->2->3->4->5要变成5->4->3->2->1。

迭代法的核心是三个指针：pre表示当前节点的前一个节点，cur表示当前节点，temp用于暂存cur的下一个节点。完整代码：

ListNode* reverseList(ListNode* head) { ListNode* cur = head; ListNode* pre = nullptr; while (cur != nullptr) { ListNode* temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; }

我来拆解一下为什么非要有temp。反转的本质是让当前节点的next指向它的前一个节点，也就是执行cur->next = pre。问题在于，一旦执行这条语句，cur原本的next就丢了。如果不先把cur->next保存到temp里，你根本没法继续往后遍历。

整个循环过程可以想象成一条队伍在向后转：每到一个人，就把他前面的人记住，让他转过身去，然后队伍整体往前挪一个人。等cur走到nullptr时，所有节点都已经转过身来了，pre正好停在新的头节点上。

这个过程里最难理解的一点是为什么最后返回pre而不是cur。循环结束时cur是nullptr，pre是原链表的最后一个节点，反转后这个节点就变成了新的头节点，所以返回pre。

4.2 递归法：从后往前反转

迭代相对好理解，递归就抽象一些。递归版的代码很短，但理解起来往往更费劲：

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)返回的是“去掉当前头节点之后，后半部分链表反转后的新头节点”。

下面要做的事情只有两件：把当前节点接到反转后的链表尾部，然后把当前节点的next置空。具体到代码里就是head->next->next = head和head->next = nullptr。

我当时第一次看这两行代码觉得很神奇，后来自己画了一个只有三个节点的链表才反应过来。以1->2->3为例，递归到节点3时返回3；回到节点2时，head是2，head->next是3，执行3->next = 2，再把2->next置空，链表局部变成3->2；回到节点1时，head是1，head->next是2，执行2->next = 1，再把1->next置空，链表变成3->2->1。

这个过程中最关键的是“信任递归返回的结果”。不要试图在脑子里模拟所有递归栈，只需要相信它返回了反转后的头节点，再专注处理当前节点和它下一个节点之间的关系，代码就顺了。

4.3 两种解法的取舍

迭代的时间复杂度是O(n)，空间复杂度是O(1)。递归的时间复杂度同样是O(n)，但空间复杂度是O(n)，因为递归栈的深度就是链表的长度。

如果只看代码美感，递归更简洁；但从工程角度讲，当链表非常长时，递归有栈溢出的风险。面试时如果先写迭代版，面试官问“能不能用递归再做一次”，你可以补上；如果一开始写递归，被问“空间复杂度能不能降到O(1)”，你也得能切回迭代版。所以两种都值得会，而且都要能默写出来。

另外一个小细节：反转链表是很多链表面试题的前置技能。比如判断回文链表时，可以先找到链表中点，再把后半段反转，逐节点比较；再比如每K个一组反转链表，拆到最后还是会落到“反转一段子链表”上。第206题不是孤立的一题，它是那些复杂题的基本零件。

5. 链表题的通用方法论与避坑清单

5.1 虚拟头节点为什么永远值得考虑

连续刷完三题，我相信你已经能感受到虚拟头节点的重要性了。第203题用虚拟头节点统一删除逻辑，第707题用虚拟头节点统一空链表和非空链表，第206题虽然本身不需要虚拟头，但如果以后面试时要求“删除倒数第n个节点”，你会发现又离不开它。

虚拟头节点的作用其实只有一个：让原本没有前驱的节点变得有前驱。任何链表操作，只要涉及到“改前驱的next”“删除头节点”“在头部插入”，都可以先问自己一句：用虚拟头节点能不能简化逻辑？

用和不用，代码量的差别可能不大，但代码的分支复杂度差别很大。没有虚拟头节点，你写一个if处理特殊位置；有虚拟头节点，所有位置一视同仁。我在实际刷题中反复体会到一个规律：分支越少的代码越不容易错，虚拟头节点就是减少分支最有效的手段。

5.2 边界条件自查表

链表题大部分bug不是逻辑理解错，而是边界条件没覆盖。我整理了一份自查清单，每写完一道链表题，from头到尾确认一遍：

• 空链表：head为nullptr时，循环和判断能不能安全退出
• 只有一个节点：删除、反转让结果是否正确
• 删除头节点：如果节点恰好是头，返回的链表头有没有更新
• 删除尾节点：删除后不要访问已经失效的next
• 插入位置是0：新节点能不能正确变成第一个节点
• 插入位置等于当前长度：能不能正确追加到尾部
• 操作越界索引：get和delete要返回正确结果或直接退出

这七个场景是链表题最常见的试题来源。平时刷题时不用刻意背，但提交前一定要用这七条自我检查一遍。

5.3 调试链表题的实操技巧

链表题调试起来比数组题麻烦，数组打一个下标就能找到位置，链表你要顺着指针走一遍。我的习惯是写一个打印函数：

void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { cout << cur->val << " -> "; cur = cur->next; } cout << "nullptr" << endl; }

每做完几步操作就调用一次，观察链表的形状是否符合预期。尤其是在第707题里，addAtHead、addAtIndex之后再调用printList，很快就能看出来插入位置是否偏移。

还有一个技巧是画图。我强烈建议在纸上画出每个节点和箭头，然后用手模拟指针操作。比如反转链表，画出初始箭头，再画出每一步的箭头变化，比对着屏幕盯十分钟代码有效得多。很多题目卡住的时候，画一遍图思路立刻就通了。

6. 常见问题与避坑实录

6.1 高频报错与定位方法

刷这三道题，我预测你会遇到四类高频问题，这里直接整理成速查表：

空指针其实是最容易修的。编译器或判题系统会告诉你哪一行出了问题，你只要在那一行多看两眼到底哪个指针可能是空的就行。最怕的是逻辑错误，比如反转链表出现环，这种问题不会崩溃，但会超时，因为程序永远走不到结尾。

6.2 一个典型的第707题翻车现场

我记忆很深的一次翻车是写get方法时，我把遍历起始点设成了dummyHead：

ListNode* cur = dummyHead; while (index--) { cur = cur->next; } return cur->val;

get(0)时，while不执行，cur停在dummyHead上，返回的是dummyHead的val，也就是0，而不是第一个真实节点的值。这个问题肉眼很难发现，因为测试链表第一个节点如果恰好不是0，结果就错了，而且错得很隐蔽。

这个坑的本质就是“找目标节点”和“找目标节点的前驱”出发点不同。查找类操作从dummyHead->next出发，插入删除类操作从dummyHead出发。你可以这样记忆：dummyHead是站在队伍前面的一道虚影，你要点名第一个人时，必须从第一个真实存在的人开始数；你要在某人前面插队时，必须找到他前面一位的虚影或真实成员。

6.3 关于内存管理

如果你用的是C++，还要注意手动管理内存。第707题里addAtHead、addAtIndex都new了新节点，deleteAtIndex删除了节点，但如果链表对象被销毁时没有析构函数，所有剩余节点都会泄漏。

训练营刷题时直接提交判题系统可能不检测这个，但本地练习时最好是写一个析构函数把链表整体释放掉：

~MyLinkedList() { ListNode* cur = dummyHead; while (cur != nullptr) { ListNode* next = cur->next; delete cur; cur = next; } }

另外delete之后的节点指针不会自动置空，虽然在线判题里这个问题不明显，但在本地debug时，访问一个已经delete的指针是未定义行为。养成“删完就置nullptr”的习惯，能避免很多奇怪的崩溃。

7. 最后分享一点个人习惯

三题刷完，我最想强调的还是画图。我见过太多人刷链表题时盯着代码硬推，但链表这个数据结构本身就是为“可视化”而生的，每个节点是盒子，每条next是箭头，操作就是改箭头指向。在纸上把这些画出来，所有问题都会变得具体。

我的个人习惯是刷完一道链表题之后，刻意在不看答案的情况下重写一遍。第203题和第206题代码比较短，当天睡前默写一遍；第707题代码长一些，第二天早上再默写。第一次写的时候依赖注释和提示，第二次只凭记忆完整写出来，能写对才算真正掌握了。

如果你现在卡在哪一步，不要急躁。链表本来就是靠熟能生巧的题，多删几个节点、多反转几遍，慢慢就会形成肌肉记忆。这三道题打底之后，后面那些看似复杂的链表题，你回头看会发现都是在今天这三题的基础上加了点变化而已。