1 题目描述

19. 删除链表的倒数第 N 个结点要求给定一个链表，任务是删除链表的倒数第 n 个结点，并且返回链表的头结点。

2 解题思路

本题可以通过双指针的方法来解决。具体来说，可以使用两个指针 slow 和 fast，它们都初始化在哑节点 dummy 上。fast 指针先向前移动 n + 1 步，然后两个指针同时移动，直到 fast 指针到达链表的末尾。这时，slow 指针恰好位于要删除节点的前一个位置。删除该节点后，返回哑节点的 next 指针即可。

3 Java 代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head); // 创建一个哑节点作为头结点
        ListNode fast = dummy, slow = dummy;

        // 让 fast 指针先走 n+1 步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

        // 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 删除目标节点
        slow.next = slow.next.next;

        return dummy.next;
    }
}

• 时间复杂度: O(L)，其中 L 是链表的长度。每个节点只遍历一次。
• 空间复杂度: O(1)，只用了常量级别的额外空间。

4 注意事项

• 哑节点：引入哑节点 dummy 以简化代码逻辑，避免处理头节点的特殊情况。
• 双指针：使用两个指针 slow 和 fast，fast 指针先前进 n + 1 步，确保当 fast 指针到达链表末尾时，slow 指针位于要删除节点的前一个位置。
• 删除节点：当 fast 指针到达链表末尾时，slow 指针指向要删除节点的前一个位置，通过 slow.next = slow.next.next 完成删除操作。
• 返回新头节点：返回 dummy.next 作为新的链表头节点。