企业官网建设流程全解析

1. 训练营第三天，为什么偏偏是这四道链表题

代码随想录算法训练营第三天，任务是四道链表相关的题目：203.移除链表元素、707.设计链表、206.反转链表、92.反转链表II。如果只看数量，四道题不算多，但真正做下来会发现，这四道题是按一条隐藏逻辑线排好的：先解决“链表操作的基础防线”，再让你自己手写一个链表来彻底理解结构，然后用反转把这个结构的特性吃透，最后用一道“部分反转”把你前面的理解拧成一股绳。

我在刷题群里看到不少同学第一天兴冲冲，第二天开始皱眉，到了第三天直接心态崩了。原因很简单：链表的题目不像数组题那样有天然的“下标”直觉，很多操作需要自己在脑子里模拟指针的移动。如果之前没有系统接触过链表，直接上手203和206，确实容易卡住。但反过来说，链表恰恰是算法面试里的高频考点，而且一旦掌握了套路，它是所有数据结构里最“有手就行”的一类题——比动态规划友好太多了。

这篇文章我不打算复述题解，而是想以训练营第三天的实际学习记录为切入点，把四道题背后的共同解题逻辑、我踩过的坑、以及一些题解里不会明说的判断依据讲清楚。无论你是正在跟训练营的学员，还是自己刷LeetCode的独立学习者，只要把这一篇里的思路理顺，后面遇到链表相关的题目，心里会稳很多。

2. 虚拟头结点的妙用：203.移除链表元素的真正难点

2.1 为什么要引入虚拟头结点

移除链表元素这题，乍一看非常简单：遍历链表，遇到val等于目标值的节点，就让前一个节点的next直接指向当前节点的next。这个逻辑数组里也类似，但链表有个特殊之处——如果你要删除的是头结点，你没有“前一个节点”。

这是很多初学者第一次被链表“毒打”的地方。处理方式通常有两种：一种是单独判断头结点是否要删除，如果要删就移动头指针；另一种是引入一个虚拟头结点（dummy head），让原来的头结点也变成一个“普通节点”，这样就统一了删除逻辑。

我当时用的是虚拟头结点方案，因为训练营的题解也是这么写的。虚拟头结点的本质是：你手动创建一个值为任意（常用0或-1）的节点，它的next指向原链表的头结点。这样一来，整个链表的所有节点都拥有了前驱节点，删除逻辑只需要一种写法，不需要特判头部。这是一种典型的“哨兵位”思想，后面的很多链表题都会用到。

2.2 双指针遍历的写法细节

具体实现上，我建议用cur和prev两个指针，prev指向当前节点的前一个节点，cur指向当前节点。从头开始遍历，如果cur.val等于目标值，就让prev.next跳过cur；否则prev移动到cur的位置。无论是否删除，cur都要移动到下一个节点。

这里有个容易出错的小细节：删除节点后，prev不需要移动。因为删除后，prev.next已经指向了cur的下一个节点，此时prev依然是“新当前节点”的前驱。如果这里多移动一步，就会跳过下一个节点，导致漏判。我在第一次写的时候就在这里栽了跟头——把删除分支里的prev也往后挪了，结果测试用例里连续出现两个相同值的时候，第二个值没被删掉。

另外，哨兵节点的内存释放问题。在C++里，dummy节点是new出来的，遍历完记得delete，否则会内存泄漏。训练营里用C++的同学不少，这个点经常被忽略，但不影响功能，所以很多题解干脆不提。我的建议是：刷题阶段用不用智能指针都行，但心里要清楚这个节点是自己创建的，写C++的时候别忘了清理；写Java和Python的同学就没有这个烦恼，垃圾回收机制会处理。

2.3 为什么虚拟头结点比“单独处理头结点”更好

单独处理头结点其实也能AC，代码也不复杂。但有一个问题：如果链表从头结点开始连续多个节点都要删除，单独处理头结点的写法需要写一个循环，直到头结点不是目标值或者链表为空。这个循环很容易写错边界。相比之下，虚拟头结点把“头部删空”的情况变成了“中间删节点”的普通场景，逻辑上更统一，也不容易漏。

更重要的是，这种“加一个哨兵”的思路，在707.设计链表里同样适用。训练营把203安排在第一天，很可能就是为707做铺垫的。如果203你只是背了代码，没有理解虚拟头结点的意义，那做707的时候大概率还要再卡一次。

3. 707.设计链表：把结构彻底吃透的一道题

3.1 五种操作的边界条件

设计链表要求实现五个功能：get(index)、addAtHead(val)、addAtTail(val)、addAtIndex(index, val)、deleteAtIndex(index)。这道题本质上不是为了让你写出多漂亮的算法，而是逼迫你亲手实现一个链表的所有基本操作。只有自己实现过一遍，你才会真正理解为什么很多链表题在调试时那么容易越界。

我用的定义是：链表节点包含val和next，链表类维护size和dummyHead。维护size这个变量非常关键，很多操作（尤其是get和addAtIndex）都需要先判断index是否合法，有一个size变量可以直接判断，不用每次遍历统计。

边界条件的判断是这道题的核心。我总结了一下：

• get(index)：index < 0 或 index >= size，直接返回 -1。
• addAtIndex(index, val)：index > size 则不加；index <= 0 时插入头部；index == size 时插入尾部；其他情况找到前驱节点插入。
• deleteAtIndex(index)：index < 0 或 index >= size，直接返回。

这里有同学会问，为什么addAtIndex里index == size就是尾部插入？因为链表的索引从0开始，当size等于3时，有效索引是0、1、2，而节点3正好是尾节点之后的“空位”。所以index == size恰好表示追加到末尾。

3.2 遍历逻辑的统一写法

实现的核心是“找到第index个节点的前驱节点”。不管是插入还是删除，都要先找到前驱。怎么找？从dummyHead出发，移动index步，就能到达第index个节点的前驱。

我举个例子，如果链表是 1 -> 2 -> 3，size是3，dummyHead指向1。要删除索引为1的节点（值为2），需要找到索引为1节点的前驱，即索引为0的节点。此时从dummyHead开始，移动1步，到达索引0的节点（值为1），然后让它的next指向值为2节点的next，即值为3的节点。整个过程非常机械，但你需要特别小心“移动几步”。

这里我要强调一个经验：写链表题的时候，永远画图。不要嫌麻烦，你脑子里想象的指针移动和实际发生的往往不一样，尤其是涉及到连续插入、删除的时候。训练营的A同学之前写addAtIndex时，总觉得自己已经找到了正确的位置，但测试就是报错。后来他在纸上画了两条链，一条是插入前，一条是插入后，标出prev和newNode的位置，一下就看出问题所在。

3.3 我踩过的一个隐蔽坑

我踩过的一个坑是在addAtTail时直接用了一个cur指针从头遍历到尾，然后让cur.next = newNode。这本身没问题，但问题是我忘记更新size了。get的时候一直返回-1，排查了半天才意识到是size没有自增。这种错误很蠢，但在训练营的高强度刷题节奏下非常容易犯，因为addAtTail的代码看起来太简单了，容易让人忽略维护size。

另外一个坑是deleteAtIndex时，如果删除的是最后一个节点，pre.next = pre.next.next之后，忽略了检查pre.next是否为null。虽然Java里不会报错，但如果你在delete后还试图访问删除节点的值（比如某个教程里打印被删除节点的值），就会得到null。刷题阶段建议只要删除完，就立刻把pre.next指向合适的值，不要再持有旧引用。

4. 反转链表的两种路径：206.反转链表的递归与迭代

4.1 迭代法：就地反转的核心逻辑

反转链表是链表题里最经典的题目，也是训练营第三天里含金量最高的一道。解法通常有两种：迭代和递归。迭代法的核心思路是：遍历链表，把每个节点的next指针指向前一个节点。听起来简单，但第一次写的人很容易被绕进去。

我的迭代写法是维护三个指针：prev（前驱，初始为null）、cur（当前节点，初始为head）、nextTemp（保存cur的下一个节点）。每一步处理：

1. 用nextTemp保存cur.next，因为马上要修改cur.next了，不保存就丢失了。
2. 将cur.next指向prev。
3. 将prev移动到cur。
4. 将cur移动到nextTemp。

这里最关键的是第一步和第二步。很多初学者写的时候会忘记保存下一步的节点，或者在修改cur.next之后才发现后面的链表已经丢了。你可以在纸上模拟一下，比如1 -> 2 -> 3 -> null，pre是null。第一步后pre还是null，cur是1，nextTemp是2；第二步后1的next变成null，此时1和后面断开了，如果没有nextTemp，后面的2和3就永远找不到了。

迭代法的循环条件是cur != null，最后返回prev。这个条件非常关键，退出循环时cur已经是null，而prev指向最后一个非空节点，也就是反转后的新头。

4.2 递归法：从后往前的思维切换

递归法相对难理解，但代码极短。核心思路是：先反转头结点之后的所有节点，然后让原本头结点的next节点（即反转过后的尾节点，也就是原链表的倒数第二个节点）的next指向它自己。

我之前看到递归解法时总觉得像魔法，后来想通了一个比喻：递归就像你让一个队伍从队尾开始向后转，每个人都转身，然后让你的下一个队友转过身来之后，你再把手指向他身后的方向。关键在于“信任”——你相信递归调用的返回值就是“反转后的新头”，你只需要处理当前节点和它的下一个节点之间的关系。

具体代码逻辑是：

1. 如果head为null或者head.next为null，直接返回head。
2. 调用reverse(head.next)，拿到反转后的新头newHead。
3. 此时，head.next指向原链表的第二个节点，而这个节点在反转后变成了倒数第一个节点，它的next正好是null。
4. 让head.next.next = head，把原第二个节点指向原头结点。
5. 让head.next = null，断掉旧的指向。
6. 返回newHead。

这里最难理解的是第2步，你会觉得“我还没有反转完啊，怎么就递归了？”但递归就是这样，它假设子问题已经解决。你只需要把所有状态更新放在递归调用之后即可。

4.3 迭代vs递归，训练营里该怎么选

我个人的建议是：单纯为了通过这道题，迭代法更容易写对，尤其在线面试手写代码的场景下，迭代法更不容易出错。但递归法值得理解，因为92题反转链表II用递归法会简单很多，而且很多大厂面试官会追问递归思路。

另外，递归有一个潜在的系统栈风险。如果链表的长度非常大，比如几万个节点，递归可能栈溢出。迭代法就不存在这个问题。所以如果是项目里真需要反转一个很长的链表，我优先用迭代。刷题阶段两者都可以过，建议先写迭代，再死磕递归。

5. 部分反转的进阶：92.反转链表II的思路拆解

5.1 先定位边界，再局部反转

92题要求在区间 [left, right] 内反转链表。如果你已经熟练掌握了206的迭代反转，这道题的关键就不是“怎么反转”，而是“如何在反转后把链表拼接回去”。

我的思路分三步：

1. 找到left位置的前驱节点（用prevLeft记录）。
2. 从left位置开始，反转right-left+1个节点。
3. 让prevLeft的next指向反转后的新头，让反转后的新尾的next指向原本right位置的下一个节点。

这个思路和训练营题解一致，但真正写的时候有个容易忽略的点：head可能发生变化。如果left等于1，那么反转后的新头就是整个链表的头。所以不能直接返回head，而要先判断是否修改了头部，或者干脆用dummyHead统一边界。

5.2 dummyHead在此题中为什么是“必需品”

在92题里，如果left等于1，prevLeft就是dummyHead，这样一来，不管left是不是1，处理逻辑都统一了：不需要看head是否改变，直接返回dummy.next即可。我在206里不用dummyHead也能写清楚，但在92里，如果不加dummyHead，left为1时会非常别扭——要么单独判断，要么用一个额外的标志变量记录新头。

这里也印证了一个规律：链表题里，只要有“可能修改头结点”的情况，dummyHead几乎都是最优解。203是，707是，92也是。一旦你习惯了这个套路，刷题效率会大幅提升。

5.3 部分反转的代码模板

很多题解会给出一个标准的局部反转模板：先用一个for循环把prevLeft移动到正确位置，然后用三个指针反转区间内的节点，最后连接。我建议直接把下面这个模板背下来，它兼容206和92：

public ListNode reverseBetween(ListNode head, int left, int right) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode pre = dummy; for (int i = 0; i < left - 1; i++) { pre = pre.next; } ListNode cur = pre.next; ListNode next = null; for (int i = 0; i < right - left; i++) { next = cur.next; cur.next = next.next; next.next = pre.next; pre.next = next; } return dummy.next; }

这个模板的巧妙之处在于：每次循环，把next节点“摘下来”，头插到pre后面。整个过程不需要像206那样维护prev指针，因为pre始终指向反转区间的前驱。第一眼看到这个代码可能会觉得有些绕，我建议你在纸上按题目给的例子走一遍，比如 1 -> 2 -> 3 -> 4 -> 5，left=2，right=4。走完后你会发现，区间内的节点就像剥洋葱一样，从第一个开始挨个被提到了pre后面。

5.4 为什么很多题解都强调“一趟遍历”

92题的常规解法是找到边界后反转，理论上需要两趟：一趟定位left，一趟反转。上面给的头插法其实也只用了两趟，但代码长度更短。面试时，面试官可能会问“能否只遍历一趟”，其实用递归法可以做到。但我不建议在训练营第三天就追求这个，先把基础写稳，再考虑优化，这是训练营的整体节奏。

6. 时间复杂度的横向对比：这四个题的实际运行效率

很多人刷链表题的时候不怎么关心复杂度，因为链表不像数组那样有大规模数据压力。但训练营要求每题都分析复杂度。我把四道题的复杂度列在下面，方便你对照：

707设计链表这里要特别说明：get、addAtHead、addAtTail、addAtIndex、deleteAtIndex，除了addAtHead和addAtTail在维护dummyHead和tail的特殊技巧下可以做到O(1)，其他操作因为要遍历查找，所以最坏O(n)。训练营里很多同学以为addAtHead必然是O(1)，但如果你是用dummyHead实现，addAtHead确实就是O(1)，因为dummyHead.next就是头结点，直接插入即可。

关于递归的空间复杂度，我见过不少博文写的是O(1)，这是不对的。递归调用会占用系统栈，每个递归层级都会压栈，所以最坏空间是O(n)。刷题时如果你对空间的敏感度不高，可能无所谓，但面试时被问到这个点，答错会很减分。

7. 训练营学习中的高频报错与排查策略

7.1 节点被“自引用”导致的死循环

这是我写206的时候遇到的最诡异的问题：反转后的链表的最后一个节点，它的next指向自己。具体表现是：运行测试用例时无限循环，或者打印链表时出现节点重复。

原因通常是递归反转的代码中，忘记将原头结点的next设为null。比如，如果原链表只有一个节点，反转前head.next本来就是null，没问题。但如果链表有两个节点，递归后，原头结点的next应该设为null，否则它还会指向原第二个节点，而原第二个节点已经反转并指向原头结点，这样两个节点就形成了环。

如何快速排查？我建议在反转后加一个调试打印，遍历链表20次，看是否越界。如果会无限重复，那就百分百是环。手动检查纸上的指针图比阅读代码更容易发现这个问题。

7.2 用“纸笔模拟”替代“脑内模拟”

训练营第一周最常见的问题是：代码写完了，但不知道哪里错了。链表題和数组题不一样，数组用IDE调试时可以看到index的移动，链表在调试器里的可视化效果很差。所以我的习惯是：遇到边界条件比较多或容易出环的题，一定在纸上画两个状态——操作前的链表、操作后的链表。

以92题为例，你可以在纸上画出left-1位置的节点（pre），以及反转区间内每个节点的前后关系。标出pre.next和cur在每一轮循环后的位置。不要嫌慢，训练营第三天画三四个图，每个图都画对，比盲目提交30次效率高得多。

7.3 把“越界”错误当成“边界条件没写全”的信号

很多链表题报错是null pointer exception，比如访问cur.next时cur为null。这种报错在训练营群里几乎每天都能看到。实际上，它对应的往往是代码里缺少对边界条件的判断。比如707的get中，index < 0或index >= size时直接返回-1，如果漏了index < 0的判断，在index为负的情况下，你会访问到dummyHead之前的节点，自然报错。

我的排查策略是：找到报错的那一行，向上回看三行代码，看看有没有一个if判断漏了边界。比如，如果报错点在addAtIndex中，检查是不是漏写了index > size的判断；如果在deleteAtIndex，检查是不是没判断index < 0。链表题经常是“先判断后操作”，顺序错了，问题就来了。

8. 训练营第三天之后的复盘建议

8.1 四道题的“共同套路清单”

我建议你在第三天结束时，自己写一份“链表操作套路清单”，包括以下几点：

1. 需要删除节点时，优先考虑虚拟头结点，避免单独处理“头结点即目标”的情况。
2. 手写链表设计题时，一定维护一个size变量，所有操作都先基于size判断合法性。
3. 反转区间链表时，先找前驱，再局部反转，最后拼接，dummyHead统一头部变化。
4. 递归反转时，处理好base case（head为null或head.next为null），记得把原头结点的next置空。
5. 写每个操作前，先明确需要维护的指针数量，最好在纸上画出来再动手。

这些结论不是训练营给的，而是我自己做第三天的题复盘时总结出来的。如果你只把四道题的代码记下来，不去总结，那第三天就白过了。

8.2 一道题做三遍：训练营的隐藏学习法

我自己的学习节奏很固定：第一遍，看题，限时30分钟，独立写；第二遍，看完官方题解，理解思路，合上答案重新写一遍；第三遍，隔一天再写一次，检验是否真的掌握了。训练营节奏快，很多人只做一遍就赶进度，但链表这种基础结构，不做三遍根本不牢固。

92题尤其适合三遍法：第一遍你可能根本写不出来；第二遍照着模板写；第三遍你会发现，不需要看题解，也能在10分钟内写出正确的代码。这个过程能建立起你用迭代法反转局部链表的“肌肉记忆”。

8.3 我练完这四道题后的一个明显变化

说实话，第四天开始做新题的时候，我发现自己对链表的恐惧感小了很多。以前看到“反转链表II”这种题，脑子里会觉得“头要变、尾要变、中间还要反转，太复杂了”。但练完这四道之后，我看到类似的题会先问自己几个问题：头结点会不会变？有没有interval？有没有删除？然后直接选用模板。

我建议你也可以在训练营群里找一个刷题搭子，互相讲题。不要小看讲题这个过程，我发现自己能把别人讲懂的时候，才是真正理解的时候。训练营第三天不仅是四道题，更像是链表基本功的集中突破——跨过这个坎，后面二叉树、回溯、动态规划再难，你至少不会因为基础薄弱而卡壳。