PiggyBlog
Published on

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

Authors

声明：该文通过我个人写Prompt喂给AI产出

问题描述

给定一个单链表 head 和一个整数 n，删除链表中倒数第 n 个节点，并返回链表的头节点。

原题链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

双指针法

通过双指针找到链表中倒数第 n 个节点的前驱节点，然后调整指针以删除目标节点。

具体思路

双指针法的关键在于找到倒数第 n 个节点的前驱节点。具体分析如下：

  1. 使用虚拟头节点：
    • 创建一个虚拟头节点 dummy，并将其 next 指向链表的头节点。这样可以方便处理特殊情况，比如删除的是头节点。
  2. 找到倒数第 n + 1 个节点：
    • 使用两个指针 p 和 p1，先让 p 向前移动 n 步。
    • 然后同时移动 p 和 p1，直到 p 到达链表末尾。此时 p1 指向的就是倒数第 n + 1 个节点。
  3. 删除倒数第 n 个节点：
    • 找到倒数第 n + 1 个节点后，将其 next 指针指向倒数第 n - 1 个节点，从而跳过倒数第 n 个节点。
  4. 返回结果：
    • 返回 dummy.next，即修改后的链表头节点。

公示推导

  1. 公式推导：
    • 通过公式 k + n = l，其中 k 是从头节点到目标节点的距离，n 是从目标节点到链表末尾的距离，l 是链表的长度。
    • 推导出 k = l - n，即从头节点走 k 步就能到达目标节点。
  2. 双指针的核心思想：
    • 先让一个指针 p 走 n 步，此时它距离链表末尾还剩 k 步。
    • 然后同时移动 p 和另一个指针 p1，直到 p 到达链表末尾（null）。
    • 此时 p1 正好走了 k 步，指向倒数第 n 个节点。
  3. 删除目标节点：
    • 找到倒数第 n + 1 个节点后，调整其 next 指针，跳过倒数第 n 个节点。

代码实现

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 创建虚拟头节点，方便处理删除头节点的情况
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 找到倒数第 n+1 个节点
        ListNode node = findNthFromEnd(dummy, n + 1);

        // 删除倒数第 n 个节点
        node.next = node.next.next;

        // 返回修改后的链表头节点
        return dummy.next;
    }

    // 辅助方法：找到倒数第 n 个节点
    public ListNode findNthFromEnd(ListNode head, int n) {
        ListNode p = head;

        // 先让 p 移动 n 步
        for (int i = 0; i < n; i++) {
            p = p.next;
        }

        // 同时移动 p 和 p1，直到 p 到达链表末尾
        ListNode p1 = head;
        while (p != null) {
            p1 = p1.next;
            p = p.next;
        }

        // 此时 p1 指向倒数第 n 个节点
        return p1;
    }
}

示例

链表: 1 -> 2 -> 3 -> 4 -> 5
n = 2
  • 找到倒数第 n + 1 个节点 3。
  • 删除倒数第 n 个节点 4。
  • 修改后的链表为 1 -> 2 -> 3 -> 5。

复杂度分析

  • 时间复杂度：O(n)，其中 n 是链表的长度。
    • 找到倒数第 n + 1 个节点需要 O(n) 的时间。
    • 删除节点需要 O(1) 的时间。
  • 空间复杂度：O(1)，只使用了常数级别的额外空间。
View on GitHub