企业官网建设流程全解析

训练营第三天，题目排得明明白白：203.移除链表元素、707.设计链表、206.反转链表。如果你是第一次接触链表，可能会觉得这些名字很基础，但真正上手写过一遍之后就会发现，链表的坑全藏在细节里：空指针、头节点、边界索引、断链顺序，哪个不小心都能让人debug到怀疑人生。这篇文章把这三道题放到一起做一次完整复盘，从题目拆解到代码实现，再到常见的错误和排查套路，适合正在刷LeetCode、准备面试，或者学完数据结构想动手巩固一遍的朋友参考。我会尽量把每一步背后的“为什么”也讲清楚，而不只是贴一份能通过的代码。

1. 内容整体设计与思路拆解

1.1 三道题为什么值得放在同一天练

先说一个我自己的感受：链表这个知识点，单独看每道题都觉得“还挺简单”，但合在一起练就会发现它其实是递进关系。203.移除链表元素练的是“遍历中删除节点”，这是链表最基础的操作；707.设计链表要求实现完整的链表类，覆盖插入、删除、查询各个接口，本质上是在测你对节点连接关系的整体把控；206.反转链表则是把指针操作拧到极致，考的是“怎么在O(1)空间内把方向全部反过来”。三道题串起来，基本覆盖了链表操作里最核心的几种场景：单向遍历、增删节点、逆置。

从面试角度看，链表题出现的频率非常高。很多人都听说过“链表题不难，但容易写错”，这句话是真的。面试官通常不会只考察你“会不会写”，更多是看你能不能把边界条件考虑清楚：空链表怎么处理？只有一个节点怎么处理？头节点要删怎么办？索引越界怎么返回？这些细节恰恰是这三道题反复训练的点。所以把它们放在一天里强化，是一种很高效的刻意练习方式。

1.2 链表题真正在考什么

链表操作看起来就是“改一个指针”，但背后涉及几个核心能力：

• 指针/引用的操作能力：写C++要注意指针指向哪里，写Python也要理解引用的语义，不能只是“背模板”。
• 边界条件的敏感度：链表题的错误大多发生在头和尾，比如删除头节点、在index等于链表长度时插入、反转空链表。
• 内存管理意识：C++里手动new出来的节点需要手动delete，如果只改指针不释放内存，虽然OJ上能过，但面试时会被追问。
• 画图模拟的能力：链表题最有效率的方法就是画图，把prev、cur、next三个指针在纸上转一遍，比直接写代码快得多。

我在带人刷题时经常说一句话：“数组靠下标，链表靠指针。”数组的思维惯性是随机访问，链表的思维惯性是“顺着走”，走的时候还要记得保存后续节点的地址。理解这个差别，写链表题才能摆脱数组思维。

1.3 复杂度概念先讲明白

链表和数组的对比是理解这三道题的基础。数组支持O(1)的随机访问，但插入删除需要移动元素，均摊O(n)；链表插入删除只要找到前驱节点就是O(1)，但查找某个位置需要从头遍历，最坏是O(n)。三道题里，203和206都能做到O(n)时间、O(1)额外空间；707的各个操作，除addAtHead是O(1)外，其余大多需要遍历，所以是O(n)。这些复杂度指标不需要背，理解“指针走几步”就能推出来。

2. 第一题：203.移除链表元素

2.1 先理解题目

题目要求：给定一个链表的头节点head和一个整数val，删除链表中所有满足Node.val == val的节点，返回新的头节点。比如链表是1->2->6->3->4->5->6，val=6，删除后应该是1->2->3->4->5。

最容易想到的思路是：从头遍历链表，如果某个节点的值等于val，就把前一个节点的next指向当前节点的next，然后跳过当前节点。听起来很直接，但问题来了：如果头节点本身就要删除呢？比如链表是6->6->1->2，val=6，头两个都要删，那新的头到底是谁？

这就是链表题经典的“头节点特判”问题。如果不做任何处理，就得先写一个while循环把头部连续等于val的节点都删掉，再处理后面的节点。这样写也能过，但逻辑上多了一个分支，稍不注意就会漏。更优雅的解法是引入虚拟头节点。

2.2 为什么建议用虚拟头节点

虚拟头节点（dummy node）的思想很简单：在真正的头节点前面再加一个dummy节点，dummy->next指向head。这样无论head怎么变，我们始终从dummy开始遍历，删除节点时不需要关心“当前节点是不是头节点”，因为dummy永远不会被删除。

这个技巧的价值在于消除特判。想象一下，如果没有dummy，删除头节点时需要把head指针向后移动，而删除中间节点只需要改前驱的next，这是两种不同逻辑。有了dummy之后，所有删除操作统一成“处理cur->next“，代码结构更清晰，也不容易出错。做题时多写一个dummy节点，代码可读性会好很多。

2.3 完整实现代码（C++）

我习惯用C++写这题，因为能顺带练习内存释放。代码是这样：

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; ListNode* removeElements(ListNode* head, int val) { ListNode* dummy = new ListNode(0, head); ListNode* cur = dummy; while (cur->next != nullptr) { if (cur->next->val == val) { ListNode* del = cur->next; cur->next = del->next; delete del; } else { cur = cur->next; } } return dummy->next; }

这段代码执行流程很直接：cur从dummy开始，每次检查cur->next的值。如果等于val，就把cur->next指向下下个节点，并释放被删除节点的内存；注意这里cur不要移动，因为新的cur->next也可能等于val。如果不等于val，cur才往前走一步。最后返回dummy->next，这就是删除后链表的真正头节点。

有人会问：返回前要不要把dummy释放掉？在LeetCode上不释放也能过，因为评测环境会统一回收。但在本地测试或面试手写时，我会在return前加上delete dummy，但那需要先保存dummy->next。两个版本都可以，关键是理解dummy只是辅助。

2.4 不带头节点的写法对比

我见过不少同学坚持不带头节点，写出来是：

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

对比一下就会发现，这个版本多了一段独立的“清理头部”逻辑，而且在处理完头部之后，中间逻辑和dummy版本基本一样。问题在于：如果前面连续删除的节点很多，代码容易在“删除后是否继续判断head”上出错；而且两个分支都写一遍，维护成本更高。

所以我个人强烈推荐dummy node技巧。它不只在203有用，很多链表中等难度题目都能用它简化边界判断，属于“一次学会，终身受用”的套路。

2.5 边界情况与复杂度

这题的边界情况有几种：空链表（head为nullptr）不会进入循环，返回dummy->next即nullptr；整个链表所有节点都等于val，循环把所有节点都删掉，最后返回nullptr；最后一个节点等于val，删除后cur->next变为nullptr，循环正常结束。这些情况在dummy版本里都不需要特殊写if，逻辑本身已经覆盖了。

复杂度方面，每个节点最多被访问一次，时间O(n)；除了dummy和临时指针外没有额外容器，空间O(1)。这里提一句，如果要“原地删除”链表里的元素，这个复杂度就是最优的。

2.6 Python版本对照

用Python写这题会更简洁，不需要手动管理内存，但引用概念要注意。删节点时只是让前面的节点指向后面的节点，Python的垃圾回收会处理不再被引用的对象。

class Solution: def removeElements(self, head: ListNode, val: int) -> ListNode: dummy = ListNode(0, head) cur = dummy while cur.next: if cur.next.val == val: cur.next = cur.next.next else: cur = cur.next return dummy.next

Python中cur.next = cur.next.next执行后，原来那个值为val的节点如果没有其他引用，会被垃圾回收，不需要手动释放。容易踩的坑是：赋值时右侧先取值，所以cur.next.next必须先存在，否则会报NoneType没有next属性。这也就要求while条件必须判断cur.next非空。

3. 第二题：707.设计链表

3.1 题目要求拆解

707这道题不是让你解一个函数，而是让你设计一个链表类。需要支持五个接口：

• get(index)：获取链表中第index个节点的值，如果索引无效则返回-1
• addAtHead(val)：在链表第一个元素之前添加一个值为val的节点
• addAtTail(val)：将值为val的节点追加到链表末尾
• addAtIndex(index, val)：在链表中的第index个节点之前添加值为val的节点。如果index等于链表长度，则追加到末尾；如果index大于链表长度，则不插入
• deleteAtIndex(index)：如果索引有效，则删除链表中第index个节点

我第一次看到这题觉得很简单，但写起来发现坑特别多。最大的坑就是索引的边界：index从0开始，合法范围是多少？addAtIndex里index等于size是合法的，等于size+1就不合法；deleteAtIndex里index等于size就不合法。如果对“索引到底指向第几个节点”不够清楚，写出的是错的。

3.2 数据结构设计思路

实现这个类，我依然会用到虚拟头节点。ListNode结构体保存值和next指针，MyLinkedList类里维护一个size变量记录节点数量，以及一个dummyHead作为虚拟头节点。

为什么要维护size？因为很多操作都需要判断索引是否合法，而判断依据就是当前链表的节点个数。比如get(index)需要保证index >= 0 && index < size；addAtIndex需要保证index >= 0 && index <= size。没有size，你还要先遍历一遍数一下节点数量，效率低且麻烦。

为什么还要用dummyHead？因为在头部插入、删除时，如果没有dummyHead，就要单独处理head指针的更新。有了dummyHead之后，addAtHead、delete第一个节点等等都变成“在dummyHead后面操作”，可以走统一的逻辑。这一点和203是同一个套路，说明这个技巧真的很常用。

3.3 每个接口逐个实现

先说get。实现思路是：先判断索引是否有效，无效返回-1；然后让cur从dummyHead开始，往前走index步；返回cur->next->val。这里有个容易绕晕的点：dummyHead是第0个节点前面的虚拟节点，所以从dummyHead走index步后，cur指向的是第index个节点的前一个，真正的第index个节点是cur->next。很多新人在这里会多走或少走一步，建议画图验证。

再说addAtHead和addAtTail。addAtHead可以直接用addAtIndex(0, val)实现，addAtTail可以用addAtIndex(size, val)实现。这是LeetCode官方也推荐的做法，因为代码复用可以让实现变得简短。不过面试时如果只写了addAtIndex，建议还是把addAtHead单独实现为O(1)操作，因为题目本意是想让你自己区分头部插入和尾部插入的代价。单链表里保存一个tail节点可以优化addAtTail到O(1)，但不是必须的，612这题用单链表直接遍历即可。

addAtIndex的坑最多。首先判断index是否合法，必须是index >= 0 && index <= size。然后让cur从dummyHead走到下标为index的节点之前，也就是走index步，此时cur指向待插入位置的前一个节点。新建节点，把新节点的next指向cur->next，再把cur->next指向新节点，最后size++。顺序很重要：一定不能先改cur->next再取原来的下一个节点，否则你就找不回原来的后续链表了。

deleteAtIndex要特别注意：先判断index >= 0 && index < size，然后找到待删除节点的前驱，也就是cur走到下标index前面。设置del = cur->next，cur->next = del->next，然后释放del，size--。在C++里如果不delete，每次调用都会泄漏内存，本地跑多了内存会上去；而LeetCode因为单个测试用例运行完就退出，所以看不出问题，但面试时最好体现内存管理意识。

3.4 完整代码（C++）

我把完整实现贴出来，这个版本可以直接跑过LeetCode：

class MyLinkedList { public: struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; MyLinkedList() { dummyHead = new ListNode(0); size = 0; } int get(int index) { if (index < 0 || index >= size) return -1; ListNode* cur = dummyHead; for (int i = 0; i < index; ++i) { cur = cur->next; } return cur->next->val; } void addAtHead(int val) { ListNode* newNode = new ListNode(val); newNode->next = dummyHead->next; dummyHead->next = newNode; size++; } void addAtTail(int val) { ListNode* cur = dummyHead; while (cur->next != nullptr) { cur = cur->next; } ListNode* newNode = new ListNode(val); cur->next = newNode; size++; } void addAtIndex(int index, int val) { if (index < 0 || index > size) return; ListNode* cur = dummyHead; for (int i = 0; i < index; ++i) { cur = cur->next; } ListNode* newNode = new ListNode(val); newNode->next = cur->next; cur->next = newNode; size++; } void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode* cur = dummyHead; for (int i = 0; i < index; ++i) { cur = cur->next; } ListNode* del = cur->next; cur->next = del->next; delete del; size--; } private: ListNode* dummyHead; int size; };

提示：在LeetCode上，类的析构函数不是必须写的，因为平台会回收内存。但如果是本地测试，建议补充一个析构函数遍历删除所有节点，避免内存泄漏。这不是题目要求，却是C++的良好习惯。

3.5 Python实现对照

Python版本的节点引用方式类似，但不需要delete，而且类属性get和ListNode的val都要注意命名冲突。我把核心方法都写出来：

class ListNode: def __init__(self, x=0): self.val = x self.next = None class MyLinkedList: def __init__(self): self.dummy = ListNode(0) self.size = 0 def get(self, index: int) -> int: if index < 0 or index >= self.size: return -1 cur = self.dummy for _ in range(index): cur = cur.next return cur.next.val def addAtHead(self, val: int) -> None: node = ListNode(val) node.next = self.dummy.next self.dummy.next = node self.size += 1 def addAtTail(self, val: int) -> None: cur = self.dummy while cur.next: cur = cur.next cur.next = ListNode(val) self.size += 1 def addAtIndex(self, index: int, val: int) -> None: if index < 0 or index > self.size: return cur = self.dummy for _ in range(index): cur = cur.next node = ListNode(val) node.next = cur.next cur.next = node self.size += 1 def deleteAtIndex(self, index: int) -> None: if index < 0 or index >= self.size: return cur = self.dummy for _ in range(index): cur = cur.next cur.next = cur.next.next self.size -= 1

3.6 进阶优化点

如果面试时做这题，答完基本功能后可以主动提几个优化思路。第一，增加tail指针使addAtTail达到O(1)，但代价是删除末尾节点时仍需要找到前驱，所以deleteAtIndex折半优化未必划算。第二，改成双向链表，让删除节点可以通过后继前驱直接定位，但占用空间翻倍。第三，get和addAtIndex可以在index大于size/2时从尾部向前遍历，均摊能节省一半时间。

这些优化不需要全写出来，但能体现你对链表结构的理解。面试官经常顺着这个问题追问“如果频繁在末尾插入怎么办”，提前想好tail节点的实现思路，会有很大加分。

4. 第三题：206.反转链表

4.1 题目描述与常见误区

题目只说一句话：给你单链表的头节点head，请你反转链表，并返回反转后的链表。示例：1->2->3->4->5变成5->4->3->2->1。

这道题看起来简单，但错误率很高。最常见的误区是“新开一个链表，遍历原链表头插”，这种写法时间和空间复杂度都不够好，而且不符合题目隐含的“原地反转”意图。正确做法是直接修改原链表的next方向，让它原地完成反转。

4.2 迭代反转：三指针法

迭代法的思路是用三个指针：prev、cur、next。初始时prev指向nullptr，cur指向head。每一步做三件事：先保存cur->next到next，再把cur->next指向prev，然后prev移动到cur，cur移动到next。循环结束后，prev就是反转后链表的头节点。

这里最关键的就是“先保存next再改指针”。因为当你执行cur->next = prev之后，原来cur后面的那个节点就找不到了，如果不提前用next保存，后面的节点全丢。很多第一次写的人在这里翻车，改完指针之后找不到后续节点，死循环或者断链。

写成代码是：

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; }

我建议在草稿纸上画一下。比如链表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。循环结束，prev=3，返回3。画一遍就会明白prev最后停在新的头节点上。

4.3 递归反转：用子问题思考

递归的写法很短，但理解门槛比迭代高。递归函数reverseList(head)返回“以head为头节点翻转后的新头节点”。我们在处理当前节点head时，假装head->next后面的子链表已经反转好了，反转后的新头节点newHead。此时head->next变成了原链表最后一个节点，我们需要让这个节点指向head，然后让head->next置空。

代码实现：

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; }

这个递归的终止条件是head为空或者head->next为空，因为空链表和单节点链表反转后还是它自己。理解这段代码有个小技巧：递归到最深处时，head是原链表的最后一个节点，它会被直接返回，一层层返回后，每一层都在做“把当前节点挂到已反转子链表的末尾”这件事。空间复杂度是O(n)，因为递归调用栈深度是n。

4.4 迭代法 vs 递归法对比

递归写法短、看着漂亮，但工程上要小心栈溢出。如果链表长度达到上万甚至更多，递归深度会很大，可能导致程序崩溃。迭代法没有这个问题，所以我在面试里推荐先写迭代，再提递归，讲清楚两者的空间复杂度差异。

4.5 Python版本

Python版本和C++几乎一样，但没有指针类型，直接通过对象引用操作：

class Solution: def reverseList(self, head: ListNode) -> ListNode: prev = None cur = head while cur: next_node = cur.next cur.next = prev prev = cur cur = next_node return prev

递归版本：

class Solution: def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head new_head = self.reverseList(head.next) head.next.next = head head.next = None return new_head

Python的引用在递归里和C++的指针行为一致，理解其中一个，另一个很快就能上手。

5. 常见问题与排查技巧实录

5.1 空指针与野指针问题

链表题的第一大杀手就是空指针。比如在203里，如果cur是nullptr还去访问cur->next，直接崩；在707里，如果addAtIndex时index取值非法，却仍然去遍历，也会访问到nullptr。解决方法是：在访问next前先判断当前节点是否为空。C++里尤其要注意new出来的节点可能为nullptr，需要先判断再使用。

5.2 忘记更新size导致越界

707里最常见的错误是：addAtIndex成功后忘了size++，deleteAtIndex忘了size--。这种错误不会立刻暴露，因为单次执行可能碰巧没触发Bug，但后续get、delete用size做合法性判断时会出错，导致明明链表里有节点却返回-1，或者index合法却被判为非法。排查方法很简单：每个涉及节点数量变化的方法，都在return前打印一下size，看是否符合预期。

5.3 反转链表死循环

206中的典型死循环写法是：在while里漏了cur = cur->next，或者漏了保存next。漏保存next的后果是cur->next被改成prev后，原后续节点丢失，程序访问到错误地址。我的排查技巧是：在循环开头打印一下当前prev、cur、next的值，运行一两轮就能发现问题。特别是本地debug时，用cout打印比眼睛盯代码快很多。

5.4 边界测试用例清单

刷链表题一定要有一套自己的边界用例，不用每次都从零想。我自己常用的是：

• 空链表：head == nullptr
• 单节点链表：1个节点，删除、反转都要测
• 两个节点链表：能暴露头尾连接问题
• 头节点和目标值相同：测试是否有头节点特判逻辑
• 所有节点都相同：测试连续删除场景
• index为0、index为size、index为size-1

每次写完代码，把这些case手动跑一遍，基本能消灭90%的边界Bug。

5.5 链表调试技巧

我强烈建议准备一个打印链表的辅助函数，不管写哪题都能用。C++版本：

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

Python版本类似。刷707的时候，每个方法跑完都打印一次链表，能立刻看出插入删除有没有搞错位置。另一个技巧是画图，尤其是反转链表这类题目，在纸上把prev、cur、next标出来，代码跟着图走一遍，很多错误根本不会发生。

6. 训练营第三天的一点个人体会

三道题全部写完的时候，我最大的感受是：链表题没有想象中那么“无脑”，每一步指针操作都要对“现在自己在哪个节点、下一个要操作谁”有清晰的认知。我自己的习惯是，无论再简单的题目，都会在提交前把所有边界用例手动过一遍，然后才点提交。这个习惯帮我省下了很多次“Wrong Answer”的等待时间。

如果想提升得更快，建议大家把review的焦点放在“错误模式”上，而不仅仅是“AC”。比如每次都问自己：这题错是因为没有用dummy node，还是没有保存next指针，还是size没有更新？把错误原因分类记录，后面再遇到链表题时，就会形成条件反射。这三天训练营的强度刚刚好，链表的增删查改和反转都过了一遍，看到题目时思路会清晰很多。

最后再分享一个小技巧：如果面试时遇到链表题，不用急着写代码，先和面试官确认清楚——链表是单链表还是双向链表，索引从0还是从1开始，节点值是否有特殊约束。这些事先问清楚，能省去后面大量返工。把这三道题练熟，链表的底子基本就稳了。