Leetcode-19-删除链表的倒数第N个结点📌

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

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

解题思路

这道题和之前返回中间结点的题一样，同样可以使用快慢指针和统计节点个数的方法来做。

但在这道题中，使用统计节点个数的方法来做会更简单一点，因为要删除链表中的节点是需要找到其前驱节点的。

如果使用快慢指针来做的话，相当于快指针先走 k-1 步。

// 快慢指针
 
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  // 边界判断
  if (head === null) {
    return head;
  }
 
  let fast = head;
  let slow = head;
 
  for (let i = 0; i < n; i++) {
    // 如果fast为空，表示删除的是头结点
    if (fast.next === null) return head.next;
    fast = fast.next;
  }
 
  while (fast.next !== null) {
    slow = slow.next;
    fast = fast.next;
  }
 
  // 此时快指针已经走完了，通过慢指针来删除第n个节点
  slow.next = slow.next.next;
 
  return head;
}

// 统计节点个数
 
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  // 边界判断
  if (head === null) {
    return head;
  }
 
  // 统计节点个数
  let k = 0;
  // 借助临时变量来遍历链表
  let h = head;
 
  while (h) {
    k++;
    h = h.next;
  }
 
  // 第index节点，即为需要删除的节点
  let index = k - n + 1;
  // index节点的前驱节点
  let pre = head;
 
  // 删除的是第一个节点时
  if (index === 1) return head.next;
 
  // 寻找需要删除的节点
  while (index > 2) {
    index--;
    pre = pre.next;
  }
 
  // 进行删除
  pre.next = pre.next.next;
 
  return head;
}