【忍者算法】从快慢指针到倒数查找：优雅解决链表倒数问题｜LeetCode第19题"删除链表的倒数第N个结点"
从快慢指针到倒数查找：优雅解决链表倒数问题从生活场景说起
想象你在一个漫长的队伍中，想知道自己距离队尾还有多少人。一个巧妙的方法是：让你的朋友从你所在位置往后数N步，然后你和朋友一起向后走。当朋友走到队尾时，你的位置就正好是倒数第N个。这个生活中的小技巧，正是我们今天要探讨的链表算法的灵感来源。
问题描述
LeetCode第19题"删除链表的倒数第N个结点"要求：给你一个链表的头节点 head 和一个整数 n ，请你删除链表的倒数第 n 个结点，并且返回链表的头结点。
例如：
输入：1 → 2 → 3 → 4 → 5, n = 2 输出：1 → 2 → 3 → 5解释：删除倒数第2个节点（值为4）输入：1 → 2, n = 2输出：2解释：删除倒数第2个节点（值为1）输入：1, n = 1输出：空链表解释：删除唯一的节点初步思路：两次遍历法
最直观的解法是先遍历一遍链表得到长度，然后再遍历一次删除目标节点：
public ListNode removeNthFromEnd(ListNode head, int n) { // 第一次遍历，计算链表长度 int length = 0; ListNode current = head; while (current != null) { length++; current = current.next; } // 如果要删除的是头节点 if (length == n) { return head.next; } // 找到待删除节点的前一个节点 current = head; for (int i = 0; i < length - n - 1; i++) { current = current.next; } // 执行删除操作 current.next = current.next.next; return head;}优化解法：快慢指针一次遍历
就像我们在队伍中的例子，我们可以用快慢指针在一次遍历内解决问题：
public ListNode removeNthFromEnd(ListNode head, int n) { // 创建哨兵节点，统一处理头节点的删除 ListNode dummy = new ListNode(0); dummy.next = head; // 初始化快慢指针 ListNode fast = dummy; ListNode slow = dummy; // 快指针先走n+1步（多走一步是为了让慢指针停在待删除节点的前一个位置） for (int i = 0; i <= n; i++) { fast = fast.next; } // 快慢指针同步移动 while (fast != null) { fast = fast.next; slow = slow.next; } // 执行删除操作 slow.next = slow.next.next; return dummy.next;}图解过程
例子：删除倒数第2个节点1) 初始状态：dummy → 1 → 2 → 3 → 4 → 5S,F2) 快指针先走n+1步：dummy → 1 → 2 → 3 → 4 → 5S F3) 同步移动直到快指针到末尾：dummy → 1 → 2 → 3 → 4 → 5 S F4) 删除slow.next节点：dummy → 1 → 2 → 3 → 5深入理解快慢指针解法
为什么这个方法能工作？让我们仔细分析：
[*]快指针先走n+1步，与慢指针产生n+1的距离
[*]当快指针到达末尾（null）时，慢指针正好在待删除节点的前一个位置
[*]这保证了我们总能找到待删除节点的前驱节点，便于执行删除操作
复杂度分析
两次遍历法：
[*]时间复杂度：O(L)，需要两次遍历
[*]空间复杂度：O(1)
[*]优点：直观易懂
[*]缺点：需要两次遍历
快慢指针法：
[*]时间复杂度：O(L)，只需一次遍历
[*]空间复杂度：O(1)
[*]优点：一次遍历即可完成，更优雅
[*]缺点：需要理解快慢指针的原理
技巧总结
[*]哨兵节点的使用
[*]统一了头节点的处理
[*]避免了额外的边界检查
[*]快慢指针的设计
[*]快指针先走n+1步的巧妙设计
[*]同步移动直至快指针到达末尾
[*]边界情况的处理
[*]链表长度等于n
[*]只有一个节点
[*]n等于链表长度
实际应用延伸
这种快慢指针的思想在实际开发中有很多应用：
[*]缓存淘汰算法
[*]流式数据的滑动窗口处理
[*]实时数据处理中的延迟计算
小结与思考
通过这个问题，我们学到了：
[*]如何用空间换时间（两次遍历）
[*]如何用巧妙的算法优化空间（快慢指针）
[*]哨兵节点的实用价值
[*]如何优雅处理链表的边界情况
当我们遇到类似的"倒数"问题时，可以考虑：
[*]是否可以用快慢指针解决？
[*]是否需要哨兵节点简化处理？
[*]如何在一次遍历中完成任务？
记住：有时看似复杂的问题，用合适的思维方式就能找到优雅的解决方案。
<hr>作者：忍者算法
公众号：忍者算法
我准备了一份刷题清单，以及这些题目的详细题解，覆盖了绝大部分常见面试题。我可以很负责任地说，只要你把这些题真正掌握了，80%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～
页:
[1]