1. 链表基础与LeetCode解题思路

链表作为数据结构中的基础类型，在算法面试中占据重要地位。不同于数组的连续存储特性，链表通过节点间的指针连接实现动态存储，这种特性使其在插入删除操作上具有O(1)时间复杂度优势，但随机访问效率较低。

在LeetCode链表类题目中，常见解题模式包括：

• 双指针技巧（快慢指针、前后指针）
• 虚拟头节点(dummy node)的运用
• 递归与迭代的转换
• 边界条件处理（空链表、单节点等）

提示：链表问题中，约80%的bug源于边界条件处理不当，建议先手动绘制链表操作示意图再编码。

2. 24. 两两交换链表中的节点

2.1 问题描述与示例

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。不能只是单纯改变节点内部的值，而需要实际进行节点交换。

示例： 输入：1->2->3->4 输出：2->1->4->3

2.2 迭代解法实现

def swapPairs(head): dummy = ListNode(0) dummy.next = head prev = dummy while prev.next and prev.next.next: first = prev.next second = first.next # 执行交换 prev.next = second first.next = second.next second.next = first # 移动prev指针 prev = first return dummy.next

关键点解析：

1. 使用dummy节点统一处理头节点交换
2. 维护prev指针指向待交换节点对的前驱
3. 交换时需要临时保存first和second节点的next指针
4. 循环条件确保存在两个可交换节点

2.3 递归解法实现

def swapPairs(head): if not head or not head.next: return head first = head second = head.next # 递归处理剩余链表 first.next = swapPairs(second.next) second.next = first return second

递归三要素：

• 终止条件：当前节点或下一节点为空
• 返回值：交换后的子链表头节点
• 本级任务：交换当前两个节点，并连接后续已交换的子链表

注意：递归解法空间复杂度为O(n)，当链表较长时可能导致栈溢出。

3. 19. 删除链表的倒数第N个节点

3.1 双指针经典应用

该问题要求只遍历一次链表完成操作，典型快慢指针应用场景。

def removeNthFromEnd(head, n): dummy = ListNode(0) dummy.next = head fast = slow = dummy # 快指针先走n+1步 for _ in range(n + 1): fast = fast.next # 同步移动直到快指针到达末尾 while fast: fast = fast.next slow = slow.next # 删除目标节点 slow.next = slow.next.next return dummy.next

3.2 关键细节分析

1. dummy节点处理删除头节点的情况
2. 快指针需要先走n+1步，使慢指针停留在目标节点的前驱
3. 边界情况测试：
   • 删除头节点
   • 删除尾节点
   • 链表长度等于n
   • 空链表输入

3.3 常见错误排查

1. 空指针异常：未检查fast.next是否为null
2. 删除错误节点：快指针步数不足或过多
3. 内存泄漏：某些语言需要手动释放删除的节点

4. 面试题02.07. 链表相交

4.1 问题转化与数学证明

设链表A长度为a，链表B长度为b，公共部分长度为c。

双指针解法核心思想：

• 指针pA遍历A后继续遍历B
• 指针pB遍历B后继续遍历A
• 两指针将在a + b - c步后相遇于交点

def getIntersectionNode(headA, headB): pA, pB = headA, headB while pA != pB: pA = pA.next if pA else headB pB = pB.next if pB else headA return pA

4.2 复杂度分析

• 时间复杂度：O(m+n)
• 空间复杂度：O(1)
• 比较次数：最多m+n次

4.3 边界条件验证

1. 无交点情况：最终pA和pB同时为null
2. 相同链表：直接返回头节点
3. 一个链表为空：立即返回null

5. 142. 环形链表II

5.1 Floyd判圈算法详解

该问题分为两个阶段：

1. 判断是否有环（快慢指针相遇）
2. 寻找环的入口（数学推导）

def detectCycle(head): slow = fast = head # 第一阶段：判断是否有环 while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: # 第二阶段：寻找入口 ptr = head while ptr != slow: ptr = ptr.next slow = slow.next return ptr return None

5.2 数学原理推导

设头节点到入口距离为a，入口到相遇点距离为b，环长为L：

• 慢指针路程：a + b
• 快指针路程：a + b + k*L
• 由2(a+b) = a+b+kL 得 a = (k-1)L + (L-b)
• 这意味着从相遇点和头节点同步移动必在入口相遇

5.3 工程实践注意事项

1. 内存安全：处理可能为null的next指针
2. 性能优化：避免不必要的变量赋值
3. 测试用例设计：
   • 无环链表
   • 整个链表成环
   • 环位于链表中间
   • 空链表输入

6. 链表问题通用解题技巧

6.1 调试与可视化方法

1. 打印链表辅助函数：

def printList(head): res = [] while head: res.append(str(head.val)) head = head.next print("->".join(res))

2. 手动绘制指针变化图
3. 使用LeetCode的可视化工具

6.2 高频错误模式

1. 指针丢失：修改next前未保存必要节点
2. 循环条件错误：未正确处理null指针
3. 边界条件遗漏：空链表、单节点链表等
4. 递归深度过大：链表过长导致栈溢出

6.3 性能优化策略

1. 减少不必要的变量声明
2. 优先使用迭代而非递归
3. 利用语言特性（如Python的多元赋值）
4. 提前终止条件判断

7. 进阶练习建议

1. 反转链表系列（完整反转、部分反转）
2. 链表排序问题（归并排序实现）
3. 复杂链表复制（带随机指针）
4. LRU缓存实现（哈希表+双向链表）

经验分享：建议每天保持2-3道链表题的练习节奏，重点理解指针操作的实质而非记忆代码模板。遇到问题时，先用小规模测试用例手动模拟运行过程，往往能快速定位问题所在。