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

1. 题目

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

示例 1：

img

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

进阶：你能尝试使用一趟扫描实现吗？

2. 思路

  • 已知题目要求一趟扫描实现删除联表的倒数第n个节点，因此引入哈希表记录每个节点的位置（同时看到sz的大小最多只有30个，因此哈希表可以直接使用数组进行代替）
  • 初始化dummy头指针，返回结果时则可直接返回dummy.next，考虑到可能会删除头节点，因此初始化了dummy节点作为头指针
  • 初始化list节点数组，size为32，预留了一头一尾的空间，因此是30 + 2
  • 初始化node节点用于遍历，同时初始化index用于实时获取节点的下标
  • 遍历链表并将节点根据下表index设置入list节点数组中
  • 完成遍历后，可以直接通过index - n - 1得到倒数第n个节点的前1位，通过index - n + 1得到倒数第n个节点的后1位
  • 随后通过list[index - n - 1].next = list[index - n + 1]即可删除倒数第n个节点
  • 将dummy.next作为结果链表返回

3. 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 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) {
        var dummy = new ListNode();
        dummy.next = head;

        var list = new ListNode[32];
        var node = dummy;
        var index = 0;
        while (node != null) {
            list[index] = node;
            node = node.next;
            index++;
        }

        var pre = list[index - n - 1];
        var next = list[index - n + 1];
        pre.next = next;

        return dummy.next;
    }
}

4. 复杂度

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

image-20230927234753838