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

[shownoso]

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

Difficulty: 中等

给定一个链表，删除链表的倒数第 _n _个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：

给定的 n 保证是有效的。

进阶：

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

思路

1. 使用两个指针组成窗口从而获得倒数第n个节点的位置
2. 设定一个哑节点，使其下一个节点为头；令第一个指针在哑节点处，令第二个指针先前进n步。
3. 两个指针组成窗口一起前进，直至第二个指针下一个节点为null，则第一个指针的下一个节点就是目标
4. 重设第一个指针的下一个节点组成新的链

Solution

Language: JavaScript

​/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function (head, n) {
  // 定义一个哑节点 dummy,1,2,3,4,5
  let dummy = {
    next: head
  };
  let left = dummy;
  let right = head;
  // right: 3
  while (n--) {
    right = right.next;
  }
  // right: null left: 3
  while (right) {
    right = right.next;
    left = left.next;
  }
  // left.next = 5
  left.next = left.next.next;
  return dummy.next;

};