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

1. 题目简介

难度：中等，原题链接：19. 删除链表的倒数第 N 个结点。

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

2. 问题分析

删除单链表节点，需要找到它的前驱，再让前驱跳过目标节点。倒数第 n 个节点无法直接按正向下标定位，但可以用两个相隔 n 步的指针找到它的前驱。

先在头节点之前放一个虚拟头节点 prev，它不属于原链表，只用来统一操作。这样，即使要删除第一个节点，也有一个前驱可供修改，最终返回 prev.next 即可。

fast 和 slow 都从 prev 开始，让 fast 先走 n 步，再让两个指针同步前进。当 fast 到达最后一个节点，也就是 fast.next == null 时，slow.next 正好是倒数第 n 个节点。

例如链表 1 → 2 → 3 → 4 → 5、n = 2 时，fast 先到节点 2；同步移动后，fast 停在 5，slow 停在 3。执行 slow.next = slow.next.next，就会跳过节点 4，得到 1 → 2 → 3 → 5。

3. 代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode prev = new ListNode(-1, head);
        ListNode fast = prev;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        ListNode slow = prev;
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return prev.next;
    }
}

4. 复杂度分析

• 时间复杂度：O(L)，L 是链表长度，两个指针各自只向前移动；题目中的 n 表示倒数位置。
• 空间复杂度：O(1)，只需要常数级别的额外空间，保存快慢指针。

来源：Coding 101 原文 · 免费阅读，引用请保留出处。内容使用说明