关于javascript:Leetcode-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]

解题思路

应用快慢指针。须要删除链表中的倒数第 n 个节点，就须要晓得倒数第 n+1 个节点，而后删除倒数第 n+1 个节点的后继节点即可。

应用 2 个指针，fast 指针提前走 n+1 步，slow 指针指向以后间隔 fast 倒数第 n 个节点，初始为 head。而后，fast 和 slow 同步向前走，直到 fast.next 为 null。此时，fast 为最初一个节点，slow 就是倒数第 n+1 个节点，而后只有删除 slow 的后继节点即可。

然而存在一种状况，即链表的长度为 n 时，fast 指针是后退不到 n+1 这个地位的，所以此时有两种解决思路：

• 一种计划，创立一个头节点 preHead，设置 preHead.next = head，这样就能够解决以上问题，删除倒数第 n 个节点后，返回 preHead.next 即可；
• 还有一种计划，fast 指针提前走 n 步之后，判断 fast.next 是否为 null，即 fast 是否是最初一个节点，如果是，则 head 为倒数第 n 个节点，间接删除头节点即可。如果不是，fast = fast.next，fast 再前进一步，后续按失常逻辑解决即可；

代码实现

增加 preHead 节点：

function removeNthFromEnd(head, n) {let preHead = new ListNode(0);
  preHead.next = head;
  let fast = preHead, slow = preHead;
  // 快指针先走 n+1 步
  while (n--) {fast = fast.next;}
  // 快指针和慢指针一起后退
  while (fast && fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  // 删除节点
  slow.next = slow.next.next;
  return preHead.next;
}

独自解决倒数第 n 个节点：

function removeNthFromEnd(head, n) {
  let fast = head, slow = head;
  // 快指针先走 n 步
  while (--n) {fast = fast.next}
  // 如果链表长度是 n，间接删除头节点
  if (!fast.next) return head.next;
  // 快指针再走一步
  fast = fast.next;
  // 快指针和慢指针一起后退
  while (fast && fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  // 删除节点
  slow.next = slow.next.next;
  return head;
}

工夫复杂度 O(n)，空间复杂度 O(1)。

顺便提一下

n-- 和 --n 两种写法是不一样的：

let n = 10;
// 从 9 到 0，一共循环 10 次，最终 n = -1
while(n--) {console.log("测试内容", n)
}

n = 10;
// 从 9 到 1，一共循环 9 次，最终 n = 0
while(--n) {console.log("测试内容", n)
}