1. Leetcode链表高频题实战解析

链表作为数据结构中的基础类型，在算法面试中出现的频率极高。今天我想分享自己在刷Leetcode链表专题时总结的几道经典题目解法，包括两两交换节点、删除倒数第N个节点、链表相交判断和环形链表检测。这些题目覆盖了链表操作的主要技巧点，掌握后能应对大多数链表类算法题。

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

2.1 问题分析与解法思路

这道题要求我们交换链表中相邻的两个节点，而不是仅仅交换它们的值。例如给定链表1->2->3->4，处理后应该变成2->1->4->3。

最直观的解法是使用递归：

1. 每次处理当前节点和下一个节点
2. 将当前节点指向后续处理好的链表
3. 将下一个节点指向当前节点

但递归会使用额外的栈空间，更优的解法是迭代法：

1. 使用虚拟头节点(dummy)简化边界条件处理
2. 维护三个指针：prev, curr, next
3. 每次交换curr和next节点
4. 更新prev指针指向新的节点关系

2.2 代码实现与细节处理

def swapPairs(head): dummy = ListNode(0) dummy.next = head prev = dummy while prev.next and prev.next.next: curr = prev.next next_node = curr.next # 交换节点 prev.next = next_node curr.next = next_node.next next_node.next = curr # 移动prev指针 prev = curr return dummy.next

关键细节：

1. 必须使用虚拟头节点，否则处理头两个节点时需要特殊逻辑
2. 交换前要确保curr和next_node都不为None
3. 更新prev指针时要指向交换后的前一个节点(curr)

注意：在交换节点时，一定要先保存next_node.next，否则链表关系会丢失。

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

3.1 双指针技巧应用

这道题的关键是如何在一次扫描中找到倒数第N个节点。常见的方法是使用快慢指针：

1. 快指针先走N步
2. 然后快慢指针同时前进
3. 当快指针到达末尾时，慢指针指向的就是倒数第N个节点

3.2 边界条件处理

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

常见错误：

1. 没有处理删除头节点的情况（使用dummy节点解决）
2. n大于链表长度（题目保证n有效）
3. 指针移动时未检查None

技巧：使用dummy节点可以统一处理删除头节点的情况，简化代码逻辑。

4. 面试题02.07. 链表相交

4.1 相交链表的特点分析

两个链表相交意味着从某个节点开始，它们共享相同的节点。要找出相交点，我们需要：

1. 计算两个链表的长度
2. 让较长的链表先走差值步
3. 然后同时遍历，第一个相同的节点就是交点

4.2 优化解法：双指针法

更巧妙的解法是不计算长度，通过交换遍历路径来消除长度差：

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

这个解法之所以有效，是因为：

• 如果链表相交，pA和pB会在交点相遇
• 如果链表不相交，pA和pB会同时到达None

时间复杂度O(m+n)，空间复杂度O(1)

5. 142. 环形链表II

5.1 环形链表检测原理

这道题需要找出环形链表的入口节点。使用快慢指针可以分两步解决：

1. 判断是否有环：快指针每次走两步，慢指针每次走一步，如果相遇则有环
2. 找入口节点：相遇后，将一个指针移到头部，然后两个指针每次走一步，再次相遇点就是入口

5.2 数学证明与实现

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

数学原理：

• 设头节点到入口距离为a，入口到相遇点距离为b，环长为c
• 快指针路程：a + n*c + b
• 慢指针路程：a + b
• 因为快指针速度是慢指针两倍：2(a+b) = a + n*c + b
• 化简得：a = (n-1)*c + (c - b)
• 这意味着从相遇点走c-b步就到入口

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

6.1 常用解题模式

1. 虚拟头节点：简化边界条件处理
2. 快慢指针：解决环形检测、中点查找等问题
3. 递归法：适用于链表反转等可分解问题
4. 双指针法：解决相交链表、删除节点等问题

6.2 调试与验证技巧

1. 画图辅助：在纸上画出链表结构和指针变化
2. 边界测试：空链表、单节点链表、头尾节点操作
3. 打印中间状态：在关键步骤打印指针位置和链表状态

经验分享：链表问题出错往往是因为指针操作顺序不当，建议先理清节点关系再写代码，避免直接操作导致链表断裂。

7. 常见错误与解决方法

7.1 指针丢失问题

在修改链表结构时，常见的错误是丢失节点引用。例如：

# 错误写法 curr.next = next_node.next # 先断开链接 next_node.next = curr # 此时next_node.next已经改变 # 正确写法 temp = next_node.next # 先保存 next_node.next = curr curr.next = temp

7.2 循环终止条件

在处理环形链表时，循环条件设置不当可能导致无限循环：

while fast and fast.next: # 正确检查 fast = fast.next.next slow = slow.next

7.3 内存管理

在某些语言如C++中，删除节点后需要手动释放内存：

ListNode* toDelete = slow->next; slow->next = slow->next->next; delete toDelete; // 避免内存泄漏

8. 性能优化与进阶思考

8.1 时间复杂度分析

1. 两两交换：O(n)，每个节点处理一次
2. 删除倒数第N个节点：O(n)，一次遍历
3. 链表相交：O(m+n)，最坏情况下遍历两个链表
4. 环形链表：O(n)，快指针最多绕环两次

8.2 空间复杂度优化

递归解法通常需要O(n)栈空间，而迭代解法只需要O(1)额外空间。在面试中，通常优先考虑迭代解法。

8.3 相关题目扩展

1. 反转链表（基础中的基础）
2. 合并两个有序链表
3. 复制带随机指针的链表
4. LRU缓存实现（结合哈希表和双向链表）

链表问题的核心在于理解指针操作和节点关系。通过这四道经典题目的练习，我总结出的经验是：先理清思路再写代码，多画图辅助理解，注意边界条件处理。在实际面试中，清晰的解题思路和良好的代码风格往往比直接写出最优解更重要。