删除链表的倒数第N个结点（LeetCode 19）

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

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个结点后，链表变为 1->2->3->5.
说明：给定的 n 保证有效
思路分析：
快慢指针法：
删除结点的关键在于定位到该结点的前驱结点，为了在一次遍历中就能找到倒数第 n个结点的前驱结点，需要定义两个指针：一个快指针，一个慢指针（其实更为贴切的应该叫前后指针而不是快慢指针）。
快指针比慢指针先走 n 步，然后两个指针一起后移，当快指针走到头的时候，慢指针走到倒数第 n 个结点的前驱结点

// 1. 快指针先走
// 2. 快慢指针一起走
// 3. 慢指针执行删除
var removeNthFromEnd = function(head, n) {
  const dummy = new ListNode()
  dummy.next = head
  let slow = dummy
  let fast = dummy
  while(n>0){ // 快指针先走
    fast = fast.next
    n--
  }
  while(fast.next){ // 快慢指针一起走
    fast = fast.next
    slow = slow.next
  }
  // 慢指针执行删除
  slow.next = slow.next.next
  return dummy.next
};

反转链表（LeetCode 206）

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例：
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
思路分析：
多指针法：
反转链表用到了三个指针：目标结点(cur)，目标结点的前驱结点(pre)，目标结点的后继结点(next)
其中 pre 和 cur 进行反转，next 是用来缓存 cur 下一步的位置

// 1.每次反转的是 cur 和 pre
// 2.cur 通过 next 后移
// 3.反转到最后 pre 变为头结点
var reverseList = function(head) {
  let pre = null 
  let cur = head
  while(cur){
    let next = cur.next
    cur.next = pre
    pre = cur
    cur = next
  }
  return pre
};

反转链表 II（LeetCode 92）

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。

说明：1 ≤ m ≤ n ≤ 链表长度
示例：
输入： 1->2->3->4->5 ，left = 2, right = 4
输出：1->4->3->2->5
思路分析：
这道题目的核心依然是反转链表，只不过中间区间反转后要和前后结点拼接起来
所以分为三步：

1. 移动到反转区间并缓存相应的结点
2. 反转设定的区间
3. 与两头结点拼合

   ar reverseBetween = function(head, left, right) {
   const dummy = new ListNode()
   dummy.next = head
   let p = dummy
   for(let i=0; i<left-1; i++){ // 移动到left的前驱结点
    p = p.next
   }
   let leftHead = p
   let start = leftHead.next
   // 反转区间
   let pre = start
   let cur = pre.next
   for(let j=0; j<right-left; j++){
    let next = cur.next
    cur.next = pre
    pre = cur
    cur = next 
   }
   // 拼接两头
   leftHead.next = pre
   start.next = cur
   return dummy.next
   };