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

Date：2019-3-31

题目地址：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/comments/

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：

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

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
提示：Maintain two pointers and update one with a delay of n steps.
使用快慢指针的方法
解题思路：**
这道题我们实际可以有多种方法来处理：

1. 遍历一遍链表，得到链表长度 Len，再从头往后走 Len - n 步就可以找到要删除的节点了
2. 维护两个指针一个指针（慢指针）指向 head 从头开始，另一个指针从 head 的 n（快）开始【如果默认的快指针是null的话，则是删除的是第一个】然后一直走到最后，慢指针指向的就是需要删除的节点的上一个节点，因为

解题：

方法1

const removeNthFromEnd = (head, n) => {
  if (!head) {
    return null;
  }
  // 先遍历一遍链表，获取总长度
  let listLength = 0
  let h = head
  while (h != null) {
    listLength++
    h = h.next
  }
  // n大于等于链表长度，直接返回 head.next => [null]
  if (n >= listLength) {
    return head.next
  }
  // 删除第 listLength - n 个节点
  let cur = head
  for (var i = 0; i < listLength - n - 1; i++) {
    cur = cur.next
  }
  let delNode = cur.next
  cur.next = delNode.next
  return head
};

方法2

const removeNthFromEnd = (head, n) => {
  let first = head
  let second = head
  while (n > 0){
    first = first.next
    n--
  }    
  if (!first) {
    return head.next
  }
  while (first.next) {
    first = first.next
    second = second.next
  }

  second.next = second.next.next
  return head
}

使用场景：

当我们遇到要从某个链表中剔除掉哪个节点的时候会用到，在业务端会经常遇到这种需求，删除某一项，或增加某一项，上面的方法可以让我们更加便捷的删除掉链表中的某一位