19. 删除链表的倒数第N个结点#

从生活场景说起#

想象你在一个漫长的队伍中，想知道自己距离队尾还有多少人。一个巧妙的方法是：让你的朋友从你所在位置往后数N步，然后你和朋友一起向后走。当朋友走到队尾时，你的位置就正好是倒数第N个。这个生活中的小技巧，正是我们今天要探讨的链表算法的灵感来源。

问题描述#

题目目标#

LeetCode第19题”删除链表的倒数第N个结点”要求：给你一个链表的头节点 head 和一个整数 n ，请你删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1#

输入： 1 → 2 → 3 → 4 → 5, n = 2 输出： 1 → 2 → 3 → 5 链表示意：

输入:  1 -> 2 -> 3 -> 4 -> 5 -> null
n = 2
输出:  1 -> 2 -> 3 -> 5 -> null

text

说明： 删除倒数第2个节点（值为4）

示例 2#

输入： 1 → 2, n = 2 输出： 2 链表示意：

输入:  1 -> 2 -> null
n = 2
输出:  2 -> null

text

说明： 删除倒数第2个节点（值为1）

补充说明#

链表题的输入本质上是节点之间的连接关系，重点通常是返回处理后的头节点或目标节点。

初步思路：两次遍历法#

最直观的解法是先遍历一遍链表得到长度，然后再遍历一次删除目标节点：

public ListNode removeNthFromEnd(ListNode head, int n) {
    // length：链表总长度
    int length = 0;
    // current：遍历指针，用于统计长度
    ListNode current = head;
    while (current != null) {
        length++;
        current = current.next;
    }

    // 若 length == n，说明要删除的是头节点（倒数第 n 个即正数第 1 个）
    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;
}

java

优化解法：快慢指针一次遍历#

就像我们在队伍中的例子，我们可以用快慢指针在一次遍历内解决问题：

public ListNode removeNthFromEnd(ListNode head, int n) {
    // dummy：哨兵节点，统一处理“删除头节点”等边界情况
    ListNode dummy = new ListNode(0);
    // 把原链表挂在哨兵后
    dummy.next = head;

    // fast/slow 都从 dummy 出发
    ListNode fast = dummy;
    ListNode slow = dummy;

    // fast 先走 n+1 步：这样当 fast 到达 null 时，slow 正好在待删节点前驱
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

    // fast 和 slow 同步后移，保持间距不变
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // 此时 slow.next 就是倒数第 n 个节点，执行删除
    slow.next = slow.next.next;

    // 返回真实头节点（跳过哨兵）
    return dummy.next;
}

java

图解过程#

例子：删除倒数第2个节点
1) 初始状态：
dummy → 1 → 2 → 3 → 4 → 5
S,F

2) 快指针先走n+1步：
dummy → 1 → 2 → 3 → 4 → 5
S           F

3) 同步移动直到快指针到末尾：
dummy → 1 → 2 → 3 → 4 → 5
            S           F

4) 删除slow.next节点：
dummy → 1 → 2 → 3 → 5

plaintext

深入理解快慢指针解法#

为什么这个方法能工作？让我们仔细分析：

快指针先走n+1步，与慢指针产生n+1的距离
当快指针到达末尾（null）时，慢指针正好在待删除节点的前一个位置
这保证了我们总能找到待删除节点的前驱节点，便于执行删除操作

复杂度分析#

两次遍历法：

时间复杂度：O(L)，需要两次遍历
空间复杂度：O(1)
优点：直观易懂
缺点：需要两次遍历

快慢指针法：

时间复杂度：O(L)，只需一次遍历
空间复杂度：O(1)
优点：一次遍历即可完成，更优雅
缺点：需要理解快慢指针的原理

技巧总结#

哨兵节点的使用
- 统一了头节点的处理
- 避免了额外的边界检查
快慢指针的设计
- 快指针先走n+1步的巧妙设计
- 同步移动直至快指针到达末尾
边界情况的处理
- 链表长度等于n
- 只有一个节点
- n等于链表长度

实际应用延伸#

这种快慢指针的思想在实际开发中有很多应用：

缓存淘汰算法
流式数据的滑动窗口处理
实时数据处理中的延迟计算

小结与思考#

通过这个问题，我们学到了：

如何用空间换时间（两次遍历）
如何用巧妙的算法优化空间（快慢指针）
哨兵节点的实用价值
如何优雅处理链表的边界情况

当我们遇到类似的”倒数”问题时，可以考虑：

是否可以用快慢指针解决？
是否需要哨兵节点简化处理？
如何在一次遍历中完成任务？

记住：有时看似复杂的问题，用合适的思维方式就能找到优雅的解决方案。