企业官网建设流程全解析

我写算法题写到第三天，终于碰到了一类让很多人头疼的结构——链表。数组和字符串再怎么折腾，至少内存是连续的，逻辑上也直来直去；链表不一样，每个节点靠自己分配出来，节点之间用指针串联，稍不注意就会把链给弄断。这一篇把链表基础、移除元素、设计链表和链表反转这几道经典题完整记录一下，包括我的思考过程、写代码时踩的坑、以及调整后的最终解法。如果你也刚学到链表，这篇可以作为一份详细的学习笔记参考。

1. 链表和数组的本质差异，为什么刷题要先补这块基础

链表题看上去代码不长，但初学者往往卡在“脑子里想明白了，一写就乱”。原因不是语法不熟，而是对链表的物理结构缺少直观认识。

1.1 内存布局不同，导致操作逻辑完全不同

数组在内存里是一块连续区域，arr[i]可以直接通过地址偏移找到，随机访问是O(1)。链表不一样，每个节点可能分散在不同位置，节点里保存着指向下一个节点的指针，想找到第n个节点必须从头逐个走一遍，时间复杂度是O(n)。

ListNode的定义在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) {} };

每个节点有两个信息：自己存的值、指向下一个节点的指针。这个结构决定了所有链表操作都必须围绕“指针的重新指向”来做，而不是像数组那样直接移动数据。

1.2 插入删除的复杂度优势与代价

数组中间插入或删除元素，需要把后续元素整体移动，时间复杂度O(n)；链表只要找到目标位置的前一个节点，改两条指针就行，时间复杂度O(1)（前提是已经定位到了）。但代价是链表无法随机访问，也没有内置的大小属性，必须遍历计数。

刷题时经常看到“链表的题目往往比数组更绕”，绕在哪？绕在指针的指向变化是隐式的。数组的移动看得见，链表的指针变化只发生在节点内部，调试时看到的是一堆地址，很难直观判断链是否接对。

1.3 实际写题时最需要建立的直观感

我的体会是：做链表题之前，先学会画图。纸上画三个节点A、B、C，标出next指向，再做插入、删除操作，把每个指针的变化一步步画出来。这个习惯能帮你解决70%的问题，因为大部分链表题就是考“指针重接的顺序”有没有搞对。

画图时特别注意：删除某个节点，不是说把这个节点本身清空，而是让它的前一个节点跳过它，直接指向后一个节点。被跳过的节点如果没有被手动释放，就变成了一个不可达的内存块，也就是所谓的“悬空”节点。刷题时通常不要求释放内存，但工程上这是必须处理的问题。

2. 移除链表元素：虚拟头节点是怎么解决“头节点特殊”这个麻烦的

LeetCode第203题，移除链表元素，题目其实很简单：删除链表中等于给定值的所有节点。但这道题第一次写，很多人都会在头节点上翻车。

2.1 最直观的思路与它的尴尬之处

最直接的思路是：遍历链表，用cur表示当前节点，pre表示cur的前一个节点。如果要删除cur，就把pre->next接到cur->next上。

这个思路对中间节点和尾节点都成立，但一遇到头节点就出问题：头节点没有前一个节点。如果头节点的值刚好等于目标值，就必须单独写一段逻辑，让头节点向后移动一位，比如：

while (head != nullptr && head->val == val) { head = head->next; }

然后才能从新的头开始遍历后续节点。很多初学者直接只写了一个while循环，结果发现头节点删除之后，后面的节点如果连续等于目标值，又漏掉了，因为head更新后没有立即再检查。

2.2 虚拟头节点为什么是更统一的解法

既然头节点的特殊之处在于没有前驱，那就给它造一个前驱：在头节点之前加一个虚拟节点dummyHead，它的值无所谓，只要它的next指向原来的头节点就行。这样所有节点都变得“有前驱”了，删除逻辑可以完全统一，不再需要专门处理头节点。

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) { cur->next = cur->next->next; } else { cur = cur->next; } } return dummyHead->next; }

注意这里遍历的是cur，但判断和修改的是cur->next，因为我们要删除cur->next这个节点时，需要保持cur不动，直接把cur->next指向下下个节点。如果cur在删除后也移动，就会漏判连续重复值的情况。

2.3 运行时内存的处理

题目给的代码环境里通常没有内存释放的要求，但在实际项目中，被删除的节点如果不再使用，应该用delete释放。

ListNode* toDelete = cur->next; cur->next = cur->next->next; delete toDelete;

顺序很重要：先保存待删除节点的地址，再修改指针，最后释放。如果先delete再修改cur->next，访问到的就是已释放的内存，程序会崩溃或行为不确定。

2.4 虚拟头节点思维在其它题目中的延展

去除重复元素、删除倒数第N个节点、两两交换节点等题目，都可以用同一个思路：把“头节点需要特殊处理”变成“所有节点统一处理”。这本质上是一种“加哨兵简化边界条件”的编程思想，不只在链表里能用，在其它需要处理边界情况的算法设计中也很常见。

3. 设计链表：把增删改查完整做一遍，边界条件全在这里

LeetCode第707题“设计链表”要求实现一个链表类，支持获取第n个节点值、头尾插入、指定位置插入删除等方法。很多人觉得这题不如算法题酷，但它恰恰能把链表操作的边界条件一次练透。

3.1 设计前的决策：单向还是双向，带不带虚拟头

题目没有强制要求单向还是双向。我的选择是：单向链表加虚拟头节点，同时维护一个size变量记录链表长度。这样写代码最直接，也不需要处理复杂的前驱指针。

类的大致结构如下：

class MyLinkedList { private: struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; ListNode* dummyHead; int size; public: MyLinkedList() { dummyHead = new ListNode(0); size = 0; } // 其它方法 };

这里dummyHead永远是“第0个节点”，真实的头节点是dummyHead->next。size表示真实节点的数量。

3.2 每个方法的实现逻辑与易错点

获取第index个节点的值：先判断index是否合法（index < 0 || index >= size直接返回-1），然后从头找到第index个节点。注意从dummyHead->next开始数，走index步就到了目标节点。

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

头部插入：先判断cur不是空指针再操作。这里cur = cur->next的那次移动，必须放在判断之前还是之后，要看循环怎么写。上面写法是把cur移到下一个节点后再判断，这样每一轮判断的都是新节点，不会漏。

如果不细想，很容易写出while (index--)里的判断逻辑不对的版本。实际运行时会发现，越界判断不到。所以设计链表这题，标准操作是先保存前一个节点。

3.3 完整的增删改查实现

在index位置前插入节点：

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

删除第index个节点：

void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode* pre = dummyHead; while (index--) { pre = pre->next; } ListNode* toDelete = pre->next; pre->next = pre->next->next; delete toDelete; size--; }

这里每一步找的都是pre，也就是待操作节点的前一个节点，这是链表操作里最重要的习惯：插入和删除，操作对象永远是前一个节点，而不是当前节点。

3.4 测试中发现的问题：addAtHead和addAtTail的实现细节

addAtHead可以复用addAtIndex(0, val)；addAtTail可以复用addAtIndex(size, val)。如果你把addAtIndex先写对，这两个方法只需要一行调用。

这个题目让我体会最深的一点是：size变量很容易忘更新。增删都涉及size的改变。之前测试时发现insert之后get的返回值不对，排查下来就是size没加，导致get判断越界时直接返回了-1。

边界条件还有：addAtIndex的index可以等于size，表示在末尾追加；index大于size则直接忽略；index小于0则按0处理。这些如果不做判断，运行时会崩或者行为不符合题意。LeetCode的判题系统对这类联想测试很严格，一错就报错，正好逼你把边界条件补齐。

4. 链表反转：迭代法的指针变化逻辑

LeetCode第206题，反转链表，是链表题里最经典的一题。第一次做的时候，我的思路是把所有节点的next都反过来指，但怎么写都觉得别扭。

4.1 双指针迭代法：cur和pre如何一步步改变

确定两个指针：pre和cur。初始时pre指向nullptr，cur指向head。遍历过程中，每一轮做三件事：

1. 保存cur->next，防止改完next后丢失链表后续部分。
2. 把cur->next指向pre，完成当前节点指针反转。
3. pre和cur都向前移动。

代码写法：

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

关键在第1步：temp保存当前节点的下一个节点。如果你不保存就改cur->next，那原本的后继节点就找不到了，整个链表剩下的部分就断了。这是链表操作中最经典也最容易犯的错误。

4.2 为什么返回值是pre而不是cur

循环结束时，cur已经变成nullptr，说明已经走到链表尾部后面去了；pre指向原来的最后一个节点，这个节点变成反转后的头节点，所以要返回pre。

如果把head->next看成是链表的“首尾连接点”，那反转这个操作本质上就是不断把“当前节点”的箭头转到“前一个节点”上。每次改变一个箭头，原来的下一个节点就暂时被temp保存住，等下一轮处理。

4.3 这题和设计链表题的联系

设计链表题练的是“怎么在一个链表里准确找到前驱、怎么插入删除而不损坏链表结构”；反转链表练的是“怎么在遍历中同时维护两个指针并且不让链表断裂”。两题合起来，链表基础操作的两个核心能力就都覆盖了。做完这两题，再去做删除倒数第N个节点、判断回文链表、环形链表，会顺畅很多。

4.4 关于递归解法的一点理解

递归版本代码很短：

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->next->next = head这一步，是让原本的下一个节点反过来指向自己；再把head->next置空，防止形成环。

我第一次写递归版本时，总纠结“newHead到底是谁”，后来明白：递归一直递归到最后一个节点，这个节点成为整个反转链表的头节点，然后一路返回到最外层。中间每个节点都负责让它的后继节点指向自己。

我的建议是：迭代法必须熟练掌握，递归法理解原理就行。面试和实际工作中，迭代法更好解释、也更不容易写错。

5. 链表题踩坑总结与调试技巧

刷完这几道题，总结一些大概率会踩的坑，以及排查方法。

5.1 空指针问题是最常见崩溃原因

很多崩溃都是因为对一个nullptr访问了next或val。比如cur->next为空时，还去访问cur->next->val。所以在做链表题时，凡是访问节点的成员，第一反应是检查这个节点是否可能为空。

5.2 指针自画图调试法

如果代码跑出来结果不对，不要急着看标准答案。我的方法是拿一个短的链表，比如dummy->1->2->3，在纸上手动模拟每一轮循环的指针变化。几乎每一轮都能找出问题所在。这个方法可能比用调试器更直观，因为链表的问题本质上是“指针变化顺序”的问题，画图能直接暴露顺序搞错的环节。

5.3 判题系统边界测试的好处

LeetCode的测试用例覆盖了空链表、单节点链表、目标值在末尾、连续重复值等情况。第一次提交如果没过，看看被卡住的是哪种用例，往往就能定位到是哪类边界条件没处理。我测试“移除链表元素”这题时，漏掉的就是连续头节点都为目标值时，while循环只判断了一次，改成循环判断才通过。

5.4 链表操作的一个通法

在写了几天链表题之后，我的经验是：链表操作基本都可以总结成“先保存后继，再改指针”。无论是删除节点、反转链表、还是插入节点，核心都是这一个动作。遇到新题先想清楚：如果需要修改某个节点的next，那涉及几个节点，谁的后继先被保存，交换的顺序是什么。想清楚再写代码，错误会少很多。

最后的个人看法：链表这块如果只刷一两题，很容易觉得自己会了，结果隔几天再来一道又卡住。比较好的办法是把这四道题作为一组练习连续完成：先移除元素（虚拟头节点）、再设计链表（完整增删改查）、然后反转链表（指针动态变化）。做完之后，链表基础就算真正打牢了，后面再碰复杂链表题，心态会稳很多。