1. 链表基础与算法训练营概览

链表作为数据结构中的经典类型，在算法面试和实际工程中都有着广泛应用。代码随想录算法训练营第三天的内容聚焦链表操作的三个核心问题：元素移除、链表设计和反转操作。这三个题目看似简单，却涵盖了链表处理中最关键的指针操作技巧。

我在刷题和面试辅导过程中发现，90%的链表问题错误都源于对指针操作的理解不足。特别是像"移除链表元素"这样的基础题目，很多求职者会忽略虚拟头节点的使用，导致边界条件处理出错。而"设计链表"则考验对链表各种操作的完整实现能力，是检验基本功的试金石。

2. 203.移除链表元素深度解析

2.1 问题本质与解法选择

题目要求删除链表中所有值等于给定val的节点，返回新头节点。表面看是简单的遍历删除，实则暗藏多个陷阱：

1. 头节点就是要删除的元素时，如何处理？
2. 连续多个节点都需要删除时，指针如何正确跳转？
3. 如何保证删除操作不影响遍历过程？

我推荐使用虚拟头节点(dummy node)解法，这是处理链表删除问题最稳健的方式。通过在真实头节点前添加一个dummy节点，可以统一处理所有节点的删除逻辑，避免对头节点的特殊处理。

class Solution: def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]: dummy = ListNode(0, head) # 创建虚拟头节点 curr = dummy while curr.next: if curr.next.val == val: curr.next = curr.next.next # 跳过目标节点 else: curr = curr.next # 正常移动指针 return dummy.next # 返回真实头节点

2.2 关键操作细节与易错点

注意：删除操作必须通过前驱节点进行，无法直接删除当前节点。这是链表结构的固有特性。

实际操作中常见以下错误：

1. 遍历时使用while curr而非while curr.next，导致无法访问前驱节点
2. 删除节点后错误移动指针，造成跳过检查或空指针异常
3. 忘记处理链表全为删除元素的特殊情况

我在面试中常让候选人手写这段代码，发现即使有经验的工程师也经常在指针移动上犯错。正确的做法是：只有在不删除时才移动curr指针，删除时只修改next指针。

3. 707.设计链表完整实现指南

3.1 链表ADT设计要点

这道题要求实现完整的链表类，包括：

• get(index)：获取第index个节点的值
• addAtHead(val)：头部插入
• addAtTail(val)：尾部插入
• addAtIndex(index,val)：指定位置插入
• deleteAtIndex(index)：删除指定位置节点

实现时需要考虑：

1. 选择单链表还是双链表（本题单链表即可）
2. 维护链表长度变量以减少时间复杂度
3. 所有操作都要处理无效index的情况

3.2 核心方法实现技巧

以addAtIndex为例，正确实现需要严格处理以下情况：

def addAtIndex(self, index: int, val: int) -> None: if index < 0 or index > self.size: return if index == 0: self.addAtHead(val) return prev = self.head for _ in range(index): prev = prev.next new_node = ListNode(val) new_node.next = prev.next prev.next = new_node self.size += 1

关键细节：

1. 先检查index有效性（0 <= index <= size）
2. 使用size变量避免重复计算长度
3. 插入位置为0时直接调用addAtHead
4. 找到插入位置的前驱节点后再操作

经验：设计链表时，所有修改操作后都要记得更新size计数器，这是面试官常检查的点。

4. 206.反转链表的多解法对比

4.1 迭代法：指针操作的艺术

最经典的解法是用三个指针逐步反转：

def reverseList(self, head: ListNode) -> ListNode: prev = None curr = head while curr: next_temp = curr.next # 暂存后继节点 curr.next = prev # 反转指针 prev = curr # 前驱指针后移 curr = next_temp # 当前指针后移 return prev

这个解法看似简单，但指针移动顺序非常关键。我在白板coding时发现，很多面试者会搞错指针移动的顺序，导致链表断裂。正确的顺序应该是：

1. 先保存next节点
2. 再反转当前节点的指针
3. 最后移动prev和curr指针

4.2 递归法的精妙之处

递归解法展现了链表操作的另一种思维方式：

def reverseList(self, head: ListNode) -> ListNode: if not head or not head.next: return head p = self.reverseList(head.next) head.next.next = head # 反转指针 head.next = None # 断开原指针 return p

递归的base case是链表为空或只有一个节点。关键操作在于：

1. 先递归到链表末端
2. 在返回过程中逐个反转指针
3. 最后将原头节点的next置空

虽然递归代码更简洁，但在实际工程中要谨慎使用，因为递归深度可能引发栈溢出。面试时建议先写迭代法，如果面试官要求再展示递归解法。

5. 链表操作常见问题排查

5.1 指针丢失与内存问题

链表操作中最常见的问题是指针丢失导致的链表断裂或内存泄漏。例如在反转链表时，如果没有先保存next节点就直接修改curr.next，就会丢失后续链表的访问路径。

调试技巧：

1. 在关键操作前打印链表状态
2. 使用可视化工具观察指针变化
3. 对每个修改操作进行完整性检查

5.2 边界条件处理大全

经过数百次链表题目练习，我总结了这些必须检查的边界条件：

1. 空链表输入（head为None）
2. 单节点链表
3. 操作位置在头部/尾部
4. 连续重复元素处理
5. 无效索引/位置参数

例如在移除元素时，要特别测试以下case：

• 链表所有节点都需要删除
• 头节点和尾节点都需要删除
• 连续多个节点需要删除

6. 链表算法进阶训练建议

掌握了这三道基础题目后，可以挑战更复杂的链表问题：

1. 环形链表检测（快慢指针）
2. 合并两个有序链表
3. 删除倒数第N个节点
4. 相交链表查找
5. 复杂链表的复制

训练时要注意：

• 先画图理清指针关系
• 编写完备的测试用例
• 比较不同解法的时间/空间复杂度
• 记录每种题型的解题模板

我在算法教学中发现，把链表问题分解为指针操作的基本单元后，90%的难题都能迎刃而解。比如合并两个有序链表，本质上就是交替操作两个链表的指针；而环形链表检测则是快慢指针的经典应用。