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

双指针

用双指针来遍历，得到倒数第 N - 1 个结点，然后进行删除即可

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  // 虚拟头结点
  // 简化删除头结点的时候的操作
  const dummyHead = new ListNode()
  dummyHead.next = head

  let p = head

  // 先遍历 n 次
  for (let i = 0; i < n; i += 1) {
    p = p.next
  }

  // 此时head 就是 lastN 的结点
  // 但是因为要删除 lastN，所以记录 lastNPrev 即可
  let lastNPrev = dummyHead

  // 然后双指针一起移动
  // 得到 lastNPrev 所在的结点
  while (p) {
    p = p.next
    lastNPrev = lastNPrev.next
  }

  // 删除倒数第 n 个结点
  lastNPrev.next = lastNPrev.next.next

  return dummyHead.next
}

双指针 2

还是一样查找倒数第 N - 1 个结点，不过可以不用转换思维，提取一个查询的倒数第 N 个结点的方法来简化逻辑

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  // 虚拟头结点
  // 简化删除头结点的时候的操作
  const dummyHead = new ListNode()
  dummyHead.next = head

  // 通过 findNthFromEnd 找到倒数第 N+1 个结点
  const lastNPrev = findNthFromEnd(dummyHead, n + 1)

  // 删除倒数第 n 个结点
  lastNPrev.next = lastNPrev.next.next

  return dummyHead.next
}

function findNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  let p = head

  // 先遍历 n 次
  for (let i = 0; i < n; i += 1) {
    p = p.next
  }

  // 此时head 就是 lastN 的结点
  let lastN = head

  // 然后双指针一起移动
  // 得到 lastN 所在的结点
  while (p) {
    p = p.next
    lastN = lastN.next
  }

  return lastN
}