（LeetCodeHot100）19. 删除链表的倒数第 N 个结点——remove-nth-node-from-end-of-list

zhangzhang2025-12-012025-12-01

19. 删除链表的倒数第 N 个结点——remove-nth-node-from-end-of-list

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

示例 1：

1 2	输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

示例 2：

1 2	输入：head = [1], n = 1 输出：[]

示例 3：

1 2	输入：head = [1,2], n = 1 输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

我的错误代码

package com.example.leetcode;

public class removeNthEndOfTheList {
    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 fast = head;
            ListNode slow = head;
            // 让快指针先走n+1个
            for (int i = 0; i < n+1; i++) {
                if (fast == null) {
                    return null;
                }
                fast = fast.next;
            }
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
            // 此时慢指针指向倒数第N+1个
            slow.next = slow.next.next;
            return head;
        }
    }
}

链表：1→2→3→4→5（长度 5），n=5（要删除倒数第 5 个节点，也就是头节点1）；
代码执行过程：
1. 快指针先走 n+1=6 步，但链表只有 5 个节点，走第 5 步时fast就变成null，第 6 步循环里会触发return null，直接返回空（完全错误，正确应该返回2→3→4→5）；
2. 就算链表长度刚好够（比如链表1→2，n=2）：快指针先走3步？不，链表长度 2，快指针走第 1 步到2，第 2 步到null，第 3 步循环里fast==null，返回null，而正确应该返回2。

答案

答案采用了虚拟头结点的方式，以防出现要删除的结点是第一个结点：

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}