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

题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

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

题解

解法一：遍历 + 哈希表

常规思路，基于单链表的性质只能从头到尾逐个遍历，因此倒数第 n 个节点，首先需要知道一共有几个节点即链表长度 sz，然后找到倒数第 n 个节点前驱节点，即倒数第 n+1 个节点，才能删除倒数第 n 个节点。

因此，我们可以遍历一遍链表，并使用哈希表来存储节点索引和节点地址，最后索引为 sz - n 的节点即为倒数第 n 个节点的前驱节点。

ListNode* removeNthFromEnd(ListNode* head, int n) {
  std::unordered_map<int, ListNode*> hash_t;
  int sz = 0;
  while(head->next != nullptr) {
    sz++;
    hash_t[sz] = head;
    head = head->next;
  }
  if (hash_t.size() - n == 0) return hash_t[2];
  hash_t[hash_t.size() - n]->next = hash_t[hash_t.size() - n]->next->next;
  return hash_t[1];
}

当链表长度很长时，用于额外存储的哈希表也会占用较大一部分内存。

解法二：双指针

双指针法，使用两个指针 fast 和 slow，fast 先走 n 步，然后 fast 和 slow 同时走，当 fast 走到链表尾部时，slow 指向的节点即为倒数第 n 个节点的前驱节点。

为了避免删除头结点的特殊情况，可以在头结点前加一个哑结点 dummy。这样无论删除的是头节点还是其余子节点，都可以用 dummy->next 统一表达。

ListNode* removeNthFromEnd(ListNode* head, int n) {
  ListNode _Dummy(0, head);
  auto slow = &_Dummy, fast = &_Dummy;
  while (n-- > 0) {
    fast = fast->next;
  }
  while(fast->next != nullptr) {
    slow = slow->next;
    fast = fast->next;
  }
  slow->next = slow->next->next;
  return _Dummy.next;
}

总结

1. 链表特性：只能从头到尾遍历，无法回溯；删除某个节点，需要找到待删除节点的前驱节点；
2. 删除子节点和删除头节点的操作不一致，可使用增加一个虚假头节点进行统一处理，简化逻辑；