链表双指针技巧：删除倒数节点与两两交换详解

1. 链表双杀高频算法题深度解析作为一名在算法领域摸爬滚打多年的老手我深知链表操作是面试中的常客。今天我们就来手撕两道LeetCode高频经典题19.删除链表的倒数第N个结点和24.两两交换链表中的节点。这两道题看似基础但能考察你对链表操作的掌握程度也是大厂面试的保留节目。2. LeetCode 19删除链表的倒数第N个结点2.1 问题分析与思路这道题要求我们删除链表中倒数第N个节点。最直观的想法是先遍历链表得到长度再计算正数位置进行删除。但这种方法需要两次遍历时间复杂度为O(2n)。更优的解法是使用双指针技巧创建快慢两个指针都指向头节点快指针先走N步然后快慢指针同时前进直到快指针到达链表末尾此时慢指针指向的就是倒数第N个节点的前驱节点关键点使用虚拟头节点(dummy node)可以简化边界条件处理特别是当需要删除的是头节点时。2.2 代码实现与解析def removeNthFromEnd(head, n): dummy ListNode(0) dummy.next head fast slow dummy # 快指针先走n步 for _ in range(n): fast fast.next # 同时移动快慢指针 while fast.next: fast fast.next slow slow.next # 删除节点 slow.next slow.next.next return dummy.next时间复杂度O(n)只需一次遍历 空间复杂度O(1)只使用了常数个额外空间2.3 常见错误与调试技巧空指针异常当n大于链表长度时快指针可能会指向None导致后续操作出错。解决方法是在快指针移动时检查是否为None。边界条件处理当需要删除的是头节点时不使用虚拟头节点会导致代码复杂。虚拟头节点是这类问题的通用解决方案。指针移动次数确保快指针先移动n步而不是n1步这是常见的off-by-one错误。3. LeetCode 24两两交换链表中的节点3.1 问题理解与解法这道题要求我们两两交换链表中的相邻节点。例如 输入1-2-3-4 输出2-1-4-3同样使用虚拟头节点可以简化操作创建虚拟头节点指向实际头节点使用三个指针prev, first, second每次交换first和second的位置更新prev指针指向新的first节点3.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时间复杂度O(n)每个节点被处理一次 空间复杂度O(1)只使用了常数个额外空间3.3 易错点与优化建议指针更新顺序必须先更新prev.next指向second再处理first.next否则会导致链表断裂。循环条件必须同时检查prev.next和prev.next.next是否存在避免空指针异常。递归解法这道题也可以用递归解决代码更简洁但空间复杂度为O(n)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 second4. 链表操作通用技巧4.1 虚拟头节点的妙用虚拟头节点(dummy node)是解决链表问题的利器它能统一处理头节点和其他节点的操作避免空链表等边界条件的特殊处理简化指针操作逻辑4.2 双指针技巧总结快慢指针用于检测环、找中点、删除倒数第N个节点等前后指针用于反转链表、交换节点等滑动窗口用于解决子链表相关问题4.3 链表问题调试方法画图辅助在纸上画出链表结构和指针移动过程打印中间状态在关键步骤打印链表当前状态单元测试编写测试用例覆盖各种边界条件5. 进阶练习与扩展掌握了这两道题后可以尝试以下变种反转链表中的一段重排链表(L0→Ln→L1→Ln-1→...)合并K个有序链表判断链表是否有环并找出环的起点链表操作的核心在于理解指针的移动和节点间的连接关系。多练习、多画图、多思考就能逐渐掌握这类问题的解决模式。