【无标题】LeetCode题解：19. 删除链表的倒数第 N 个结点，JavaScript，详细注释

原题链接：19. 删除链表的倒数第 N 个结点

解题思路：

1. 使用快慢两个指针，它们之间的距离为n + 1。
2. 两个指针一起沿着链表从头到尾移动，当快指针移动到链表末尾时，慢指针的next指向倒数第n个节点。
3. 将倒数n+1个节点指向倒数n-1个节点，即可删除倒数第n个节点。
4. 由于head = [1], n = 1这个用例的输出为[]。为了保证能将head删除，需要设置一个prev节点，它指向原链表的head，两个指针都从prev开始移动，即可删除head。

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
  // 创建一个prev节点，next指向head
  let prev = new ListNode(null, head)
  // 用快慢两个指针移动
  let slow = prev
  let fast = prev

  // fast一直移动到链表末尾
  while (fast) {
    // 控制fast和slow之间的距离是n+1
    if (n >= 0) {
      n--
    } else {
      // 当fast和slow的距离达到n+1时，slow才开始移动
      slow = slow.next
    }

    // fast始终保持移动即可
    fast = fast.next
  }

  // 当fast移动到链表末尾时，slow.next指向倒数第n个节点
  // 将倒数n+1个节点指向倒数n-1个节点，即可删除倒数第n个节点
  slow.next = slow.next.next

  // prev.next始终指向新链表的头结点
  return prev.next
};
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
32
33