企业官网建设流程全解析

Day4打卡，我给自己安排的是 Leetcode 203 和 707，两道链表题。说实话，很多人刷链表喜欢从反转链表开始，但我的真实感受是：以 203 开头学的是“删除”，以 707 开头学的是“设计”，这两件事恰好覆盖了链表操作里大概 90% 的基础动作。203 是 Leetcode 热门 100 题里的常客，707 则是一道典型的类设计题，面试里让你手写一个链表类、现场补全几个方法的情况并不少见。

这篇文章就把两道题放在一起拆开讲，从虚拟头节点的来龙去脉，到索引边界怎么判断，再到我实际调试时踩过的坑。如果你是刚开始刷链表、或者已经刷过但总在边界条件上翻车，那这篇应该能帮你省下不少时间。

1. 为什么把 203 和 707 放在同一天刷

1.1 两道题的题型定位

Leetcode 203 题面很简单：给你一个链表的头节点 head 和一个整数 val，删除链表中所有等于 val 的节点，返回新的头节点。它的题眼不在“删除”这个动作本身，而在于“头节点也可能被删”这件事怎么处理。

Leetcode 707 则是另一类考法：题目让你设计一个链表类，自己实现 get、addAtHead、addAtTail、addAtIndex、deleteAtIndex 五个方法。表面上是设计题，实际上是把链表的增删查全部揉在一起考。这两道题放在同一天刷，本质上就是一次“链表基本功”的组合训练：一个考你删除操作的边界处理，一个考你对链表整体结构的掌握程度。

1.2 从“删除指定值”到“手写一个链表”的进阶逻辑

我推荐 203 在前、707 在后，不是随便排的。203 教会你“如何在链表中安全地删掉一个节点”，核心是前驱节点和指针跳转；707 直接把这个能力放大到五个方法，而且还要你自己维护链表的长度、索引合法性和哨兵节点。

刷完 203 再去写 707 的 deleteAtIndex，你会发现思路几乎不用切换：找前驱，跳过当前节点，接上后继。707 里的 addAtIndex 和 203 里的删除逻辑也是一对镜像操作，一个管“断开”，一个管“插入”。两道题连着刷，你会开始理解链表操作的本质：不管增还是删，永远要抓住“前驱节点”这根救命稻草。

2. Leetcode 203：移除链表元素，先搞定“头节点怎么删”

2.1 题目到底难在哪

给你示例：head = [1,2,6,3,4,5,6]，val = 6，返回结果是 [1,2,3,4,5]。前三个节点都好处理，遍历到 6 就把它跳过去。真正麻烦的是如果输入是 head = [6,6,6,1,2]，你要删掉的节点在链表最前面。

这时候你会有个直觉：如果头节点就是待删除的值，直接 head = head.next 不就行了吗？可以，但问题是删完这个头，新的头可能还是待删除的值。你就得写一个循环，先把头处理干净，再处理中间节点。代码分支一多，就容易漏一个判断，而且面试时候如果只写一种分支，很容易被追问。

2.2 虚拟头节点：把删除变成一套统一逻辑

解决这个问题最经典的办法，就是加一个虚拟头节点，也叫哨兵节点。

class Solution { public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0, head); ListNode cur = dummy; while (cur.next != null) { if (cur.next.val == val) { cur.next = cur.next.next; } else { cur = cur.next; } } return dummy.next; } }

核心思路：dummy 这个节点不存有效数据，它只是站在头节点前面。这样一来，原本“头节点可能被删所以逻辑要单写”的问题消失了。删除动作永远发生在 cur.next 上，头节点在别人眼里也只是普通节点，删法和中间节点完全一致。

要注意的是 if 分支里删除之后 cur 不能动。因为 cur.next 已经换成了新节点，这个新节点还没检查过，如果继续删除或跳过，就可能漏删连续的目标值。我见过不少新人在这一步犯错：删除后 cur = cur.next，结果 6 6 6 这种连续节点只删最后一个。这个细节是 203 最容易丢分的地方。

顺便补一句：如果不用虚拟头节点，那就要单独写while (head != null && head.val == val) head = head.next;，然后再遍历一次。不是不能写，但代码明显长了，而且每次删除要判断当前节点是不是头，心智负担更高。虚拟头节点真正解决的问题，不是“不能”删除头节点，而是让代码在逻辑上没有任何例外情况。

2.3 递归解法的思路参考

除了迭代，203 还可以用递归写，代码非常短：

class Solution { public ListNode removeElements(ListNode head, int val) { if (head == null) return null; head.next = removeElements(head.next, val); return head.val == val ? head.next : head; } }

递归怎么写：先假设后面的链表已经处理完毕，head.next 已经指向了“删完所有目标值”的链表，接下来只需要判断当前 head 自己要不要被删。如果要删，直接返回 head.next，相当于把当前节点丢弃；如果要留，就让 head.next 保持上面处理好的结果。

这个解法思路对理解“递归返回的是删好的子链表”很有帮助，但我个人不太推荐在 203 上优先用递归。原因有两个：一是链表可能很长，递归栈最深可能有 O(n)，实测 1 万节点以内问题不大，但思想就是不如迭代直观；二是在面试里更容易被追问栈溢出问题，还不如老老实实讲虚拟头节点来得稳。

2.4 203 提交时的注意点

• 返回值一定是 dummy.next，而不是 head。因为 head 可能已经被删了，dummy.next 才是真正处理完的头。
• 循环条件是 cur.next != null，不是 cur != null。因为你判断的是“下一个节点要不要删”，cur 自己是不会变的。
• 时间复杂度 O(n)，空间 O(1)。这个复杂度是链表的标配，面试脱口就能给。

3. Leetcode 707：设计链表，链表基本功的集中考试

3.1 707 到底要求什么

707 不是让你解一道算法题，而是让你实现一个 MyLinkedList 类。题目要求支持五个方法：

• get(index)：获取链表中第 index 个节点的值，索引从 0 开始，非法返回 -1。
• addAtHead(val)：在链表头部插入一个节点。
• addAtTail(val)：在链表尾部插入一个节点。
• addAtIndex(index, val)：在第 index 个节点之前插入，如果 index 等于链表长度，则插到末尾；如果 index 大于长度则不插入。
• deleteAtIndex(index)：删除第 index 个节点，非法索引直接忽略。

难点在于边界条件太多。index 可以是负数吗？题目明确说 index < 0 时按 0 处理。index 能等于 size 吗？在有 addAtIndex 时可以，等于 size 意味着追加到末尾。deleteAtIndex 时 index 等于 size 行吗？不行，因为 size 是“最后一个节点的下标 + 1”，不存在下标为 size 的节点。这些细节就是 707 的考点。

3.2 类结构设计：size 与虚拟头节点缺一不可

我写 707 时，类定义长这样：

class MyLinkedList { private ListNode dummyHead; private int size; public MyLinkedList() { dummyHead = new ListNode(0); size = 0; } // 其他方法见后面 }

两个字段各有各的用处。size 记录链表现有节点个数，是所有方法判断边界的前提。dummyHead 是哨兵，让空链表和有元素的链表共享同一套前后逻辑。比如 addAtHead 在空链表上执行时，没有 dummyHead，你就要单独讨论 head 是不是 null；有了 dummyHead，操作位置永远是 dummyHead.next，代码立刻干净了。

3.3 get 与 addAtIndex 的索引边界处理

get 的写法：

public int get(int index) { if (index < 0 || index >= size) return -1; ListNode cur = dummyHead.next; for (int i = 0; i < index; i++) { cur = cur.next; } return cur.val; }

注意循环次数。cur 已经指向第 0 个节点了，再走 index 次，正好停在 index 下标的节点上。你要是写成i < index - 1，就会少走一步，最终停在 index-1 的位置上，返回错值。这种“循环次数差一位”的问题，在链表题里最阴间，调试时还不容易看出来。

addAtIndex 是核心方法：

public void addAtIndex(int index, int val) { if (index > size) return; if (index < 0) index = 0; ListNode pred = dummyHead; for (int i = 0; i < index; i++) { pred = pred.next; } ListNode newNode = new ListNode(val); newNode.next = pred.next; pred.next = newNode; size++; }

先看边界：index > size 直接不操作，index < 0 归到 0。这里的index == size是合法场景，意味着插到末尾。再看指针：pred 从 dummyHead 出发，循环 index 次。当 index 是 0 时，循环一次都不执行，pred 还是 dummyHead，插入位置正是链表最前面；当 index 是 size 时，pred 会走到最后一个节点，newNode 接在它后面，正好是末尾。

我会建议你把“pred 走 index 步之后停在 index-1 节点的位置”这句话背下来。707 里 addAtIndex 和 deleteAtIndex 全是围绕这个结论展开的。

3.4 删除节点和 addAtHead/addAtTail 的复用思路

deleteAtIndex 的写法：

public void deleteAtIndex(int index) { if (index < 0 || index >= size) return; ListNode pred = dummyHead; for (int i = 0; i < index; i++) { pred = pred.next; } pred.next = pred.next.next; size--; }

这里的边界判断没有index > size的情况了，因为下标最大是 size - 1，等于 size 就是非法。pred 同样是走 index 步，停在要删节点的前驱。然后pred.next = pred.next.next，一句话完成删除。即使删的是最后一个节点，pred.next.next 是 null，赋值结果也是 null，不会报错，因为 pred.next 不为空，访问它的 next 是安全操作。

addAtHead 和 addAtTail 我写的很直接，就是复用 addAtIndex：

public void addAtHead(int val) { addAtIndex(0, val); } public void addAtTail(int val) { addAtIndex(size, val); }

addAtHead 等价于在 0 位置插入，addAtTail 等价于在 size 位置插入。这样写的好处是逻辑集中，所有插入的边界处理都在 addAtIndex 里完成，不容易出现两个方法各写一套导致 bug 各不同步的情况。

3.5 单链表还是双链表：707 的取舍

707 官方是支持实现成双链表的，很多题解也推双链表，理由是 addAtTail 可以做到 O(1)。我没选双链表，理由是这题的单链表版本通过率足够高，而且代码短，错误面小。

如果你想让 addAtTail 变成 O(1)，双链表固然好，但代价是每个节点都要维护 prev 和 next 两个指针，插入删除时更新关系翻倍，而且尾哨兵节点删除时如果恰好删的是 tail 指向的节点，还需要特殊处理。对于 707 这种“验收代码正确性”的题目，我的经验是先把单链表版本写顺溜，有余力再考虑双链表的性能优化，否则容易在调试里把时间耗光。

4. 两题合并刷时的高频翻车现场

4.1 前驱指针移动次数差一位

这是链表题里我最常踩的坑，没有之一。addAtIndex 要“走到第 index-1 个节点”，deleteAtIndex 也要“走到第 index-1 个节点”，但它们的循环次数其实都是 index 次，区别只在于起点是 dummyHead 还是 head.next。

画个带下标的图就能理清：dummyHead 是“第 -1 个位置”，从它出发走 1 步到下标 0 的节点，走 index 步到下标 index-1 的节点。而 get 里的 cur 从下标 0 出发，走 index 步到下标 index 的节点。两个场景差一步，所以我在写代码之前都会先在注释里写清楚“我要找的是前驱还是当前节点”，再决定循环次数。强烈建议你也这么做。

4.2 指针交接顺序导致的断链

插入节点时，很多新手会先写pred.next = newNode，再写newNode.next = pred.next。问题在于 pred.next 被改成 newNode 之后，原来 pred.next 指向的后继节点就找不到了，新节点接了个寂寞。

正确顺序是：先把 newNodede 的 next 指向 pred.next，再把 pred.next 指向 newNode。换成大白话就是“先让新人认识后面的人，再让前面的领导牵线，最后把旧人的位置换掉”。如果你喜欢更稳的写法，可以加一个临时变量：

ListNode oldNext = pred.next; pred.next = newNode; newNode.next = oldNext;

这样逻辑顺序完全可读，谁在前谁在后都不会错。我在写 707 时就是用这个写法，虽然多一行代码，但排查问题时长了不少。

4.3 size 忘记维护与越界判断错误

707 里 size 是“纪律”的化身。插入成功必须 size++，删除成功必须 size--。我见过有人 addAtHead 忘了在 addAtIndex 里加 size，导致链表长度对不上，get(size-1) 永远返回 -1；也有人 deleteAtIndex 里判断条件写成index > size，漏掉了 index == size 这个非法情况。

最保险的做法是每次写完一个方法，立刻手动跑一遍边界用例。比如链表现有 2 个节点，get(2) 应该是 -1，deleteAtIndex(2) 不应报空指针，addAtIndex(2, val) 应该成功且 size 变 3。把这几个 case 在脑子里过一遍，大多数越界问题都能提前拦住。

我自己的一个习惯是：707 写完直接在本地 mock 一组操作序列，和 Leetcode 官方例子一致，然后逐个方法打印 size 和链表内容。空链表、单节点链表、满链表各测一遍，测完再提交。这样做的成本很低，但能避免在平台上反复提交试错。

4.4 排错技巧与边界用例清单

如果在 707 里报错，可以按这个顺序自查：

• 检查 index 合法性是否用到了 size。合法区间是 get 和 delete 用0 <= index < size，addAtIndex 用0 <= index <= size。
• 检查各个方法的循环次数。get 用i < index，addAtIndex 和 deleteAtIndex 也用i < index，但它们起点不同，一个是从 head 出发，一个是从 dummyHead 出发。
• 检查是否在插入/删除后维护了 size。少一次 size++ 或 size--，整个链表长度立刻错乱。
• 检查指针交接顺序，尤其是有没有先断链再接线。

至于 203，我建议提交前先测三个经典场景：头节点就是要删的值、连续多个目标值、目标值在尾部。这三个场景覆盖了 203 最核心的边界，跑通之后再提交，基本都是一遍过。

我刷完这两道题之后有个很直接的感受：链表题的核心从来不是“遍历”本身，而是你是否清楚每个指针当前站在哪、下一步要指向谁。203 教会你虚拟头节点可以让特殊位置变成普通位置，707 教会你维护 size 索引和边界条件的重要性。这两板斧用到反转链表、删除倒数第 N 个节点、合并两个有序链表上，同样管用。

如果你也想刷，有个小建议：不要直接抄题解，先把 707 的五个方法自己在本地默写一遍，卡住的地方做标记，再回头对比代码。这个从“看明白”到“写出来”的过程，才是这两道题真正值钱的地方。