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

一、题目

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

二、题解

思路：链表 / 双指针 / 虚拟头节点

解法一：双指针

1. 核心思路

这道题要删除的是链表的倒数第 n 个节点。

如果从前往后找，我们并不知道倒数第 n 个节点在哪里。

所以可以使用快慢指针：

  • 让 fast 指针先走 n 步；
  • 然后 fast 和 slow 一起走；
  • 当 fast 到达链表末尾时，slow 正好停在要删除节点的前一个节点；
  • 最后执行 slow.next = slow.next.next，删除目标节点。

为了方便处理删除头节点的情况，使用虚拟头节点 dummy。

2. 具体步骤

  1. 创建虚拟头节点 dummy，让 dummy.next = head。
  2. 定义快慢指针 fast 和 slow，都从 dummy 出发。
  3. 让 fast 先向后走 n 步。
  4. 然后让 fast 和 slow 同时向后移动。
  5. 当 fast.next == null 时，说明 fast 已经到达最后一个节点，此时 slow.next 就是要删除的节点。
  6. 执行 slow.next = slow.next.next 删除节点。
  7. 返回 dummy.next。

3. 关键逻辑

关键是让 fast 和 slow 之间始终保持 n 个节点的距离。

例如：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
n = 2

先让 fast 走 2 步：

slow
 ↓
dummy -> 1 -> 2 -> 3 -> 4 -> 5
              ↑
             fast

然后 fast 和 slow 一起走，直到 fast.next == null：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
                   ↑         ↑
		          slow      fast

此时 slow 在节点 3，slow.next 是节点 4，也就是要删除的节点。

所以执行：

slow.next = slow.next.next;

即可删除节点 4。

4. 代码

/**
 * 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) {
        // 1. 创建虚拟头节点，方便处理删除头节点的情况
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // 2. 定义快慢指针，都从 dummy 出发
        ListNode fast = dummy;
        ListNode slow = dummy;

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

        // 4. fast 和 slow 一起走
        // 当 fast 到达最后一个节点时，slow 正好在待删除节点的前一个节点
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 5. 删除 slow 后面的节点
        slow.next = slow.next.next;

        // 6. 返回真正的头节点
        return dummy.next;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：链表中的每个节点最多被访问一次，因此时间复杂度是 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：只使用了 dummy、fast、slow 等常数个额外变量，因此空间复杂度是 O(1)O(1)。

解法二：先求链表长度

思路：链表 / 模拟 / 虚拟头节点

1. 核心思路

这道题也可以先求出链表的长度 len。

如果链表长度是 len，要删除倒数第 n 个节点，那么它就是正数第：

len - n + 1

个节点。

但是删除链表节点时，需要找到它的前一个节点。

所以我们真正要找到的是正数第：

len - n

个节点。

为了方便处理删除头节点的情况，仍然使用虚拟头节点 dummy。

2. 具体步骤

  1. 创建虚拟头节点 dummy，让 dummy.next = head。
  2. 遍历链表，统计链表长度 len。
  3. 从 dummy 出发，向后走 len - n 步，找到待删除节点的前一个节点。
  4. 执行 prev.next = prev.next.next 删除节点。
  5. 返回 dummy.next。

3. 关键逻辑

假设链表是：

1 -> 2 -> 3 -> 4 -> 5
n = 2

链表长度：

len = 5

要删除倒数第 2 个节点，也就是正数第：

len - n + 1 = 5 - 2 + 1 = 4

个节点，也就是节点 4。

删除节点 4，需要找到它的前一个节点，也就是正数第：

len - n = 5 - 2 = 3

个节点，也就是节点 3。

所以从 dummy 出发走 len - n 步，就能找到待删除节点的前一个节点。

4. 代码

/**
 * 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 = next; }
 * }
 */

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

        // 2. 统计链表长度
        int len = 0;
        ListNode cur = head;
        while (cur != null) {
            len++;
            cur = cur.next;
        }

        // 3. 找到待删除节点的前一个节点
        ListNode prev = dummy;
        for (int i = 0; i < len - n; i++) {
            prev = prev.next;
        }

        // 4. 删除目标节点
        prev.next = prev.next.next;

        // 5. 返回真正的头节点
        return dummy.next;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：第一次遍历链表统计长度，第二次遍历找到待删除节点的前一个节点，因此时间复杂度是 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：只使用了 dummy、cur、prev、len 等常数个额外变量，因此空间复杂度是 O(1)O(1)。

评论