【忍者算法】从快慢指针到倒数查找：优雅解决链表倒数问题｜LeetCode第19题"删除链表的倒数第N个结点"

pSzFzolZPpx2

从快慢指针到倒数查找：优雅解决链表倒数问题

从生活场景说起

想象你在一个漫长的队伍中，想知道自己距离队尾还有多少人。一个巧妙的方法是：让你的朋友从你所在位置往后数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%的算法面试都能遇到相似题目。公众号回复【刷题清单】获取～