快慢指针指的是两个一前一后的指针，两个指针往同一个方向走，只是一个快一个慢。快慢指针严格来说只能有俩，不过实际做题中，可能会出现一前、一中、一后的三个指针，这种超过两个指针的解题方法也叫“多指针法”。

快慢指针——删除链表的倒数第 N 个结点

真题描述：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个结点后，链表变为 1->2->3->5.

  1. var removeNthFromEnd = function(head, n) {
  2.     let dummy = new ListNode();
  3.     dummy.next = head;
  4.     let fast = dummy;
  5.     let slow = dummy;
  7.     while(n) {
  8.         fast = fast.next;
  9.         n--;
  10.     }
  12.     while(fast.next) {
  13.         fast = fast.next;
  14.         slow = slow.next;
  15.     }
  16.     slow.next = slow.next.next;
  17.     return dummy.next;
  18. };

多指针法——链表的反转

完全反转一个链表

真题描述：定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路解读

——处理链表的本质，是处理链表结点之间的指针关系。
快慢指针 - 图1

next 指针的指向给反过来就行了
快慢指针 - 图2

接下来我们需要琢磨的是如何去反转指针的指向，这里我们需要用到三个指针，它们分别指向目标结点（cur）、目标结点的前驱结点（pre）、目标结点的后继结点（next）。这里咱们随便找个结点来开刀：
快慢指针 - 图3

那 next 不是完全没用到吗？
当然有用，咱们反转完链表变成啥样了：
快慢指针 - 图4

要是不用 next 给你指着 cur 原本的后继结点，你上哪去定位下一个结点呢？遍历都没法继续了嗷。

咱们从第一个结点开始，每个结点都给它进行一次 next 指针的反转。到最后一个结点时，整个链表就已经被我们彻底反转掉了。

  1. /**
  2.  * @param {ListNode} head
  3.  * @return {ListNode}
  4.  */
  5. const reverseList = function(head) {
  6.     // 初始化前驱结点为 null
  7.     let pre = null;
  8.     // 初始化目标结点为头结点
  9.     let cur = head;
  10.     // 只要目标结点不为 null，遍历就得继续
  11.     while (cur !== null) {
  12.         // 记录一下 next 结点
  13.         let next = cur.next;
  14.         // 反转指针
  15.         cur.next = pre;
  16.         // pre 往前走一步
  17.         pre = cur;
  18.         // cur往前走一步
  19.         cur = next;
  20.     }
  21.     // 反转结束后，pre 就会变成新链表的头结点
  22.     return pre
  23. };

局部反转一个链表

反转链表真是座金矿，反转完整体反转局部，反转完局部还能每 k 个一组花式反转（最后这个略难，我们会放在真题训练环节来做）。虽然难度依次进阶，但只要把握住核心思想就没问题，下面咱们来看看如何反转局部：
真题描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL

思路解读

我们仍然是从指针反转来入手：

快慢指针 - 图5
按照题中的示例，假如我们需要反转的是链表的第 2-4 之间的结点，那么对应的指针逆序后会是这个样子：
快慢指针 - 图6

4指3，3指2，这都没问题，关键在于，如何让1指向4、让2指向5呢？这就要求我们在单纯的重复“逆序”这个动作之外，还需要对被逆序的区间前后的两个结点做额外的处理：
快慢指针 - 图7
由于我们遍历链表的顺序是从前往后遍历，那么为了避免结点1和结点2随着遍历向后推进被遗失，我们需要提前把1结点缓存下来。而结点5就没有这么麻烦了：随着遍历的进行，当我们完成了结点4的指针反转后，此时 cur 指针就恰好指在结点5上：
快慢指针 - 图8
此时我们直接将结点2的 next 指针指向 cur、将结点1的 next 指针指向 pre 即可。

  1. /**
  2.  * @param {ListNode} head
  3.  * @param {number} m
  4.  * @param {number} n
  5.  * @return {ListNode}
  6.  */
  7. // 入参是头结点、m、n
  8. const reverseBetween = function(head, m, n) {
  9.     // 定义pre、cur，用leftHead来承接整个区间的前驱结点
  10.     let pre,cur,leftHead
  11.     // 别忘了用 dummy 嗷
  12.     const dummy = new ListNode()  
  13.     // dummy后继结点是头结点
  14.     dummy.next = head
  15.     // p是一个游标，用于遍历，最初指向 dummy
  16.     let p = dummy  
  17.     // p往前走 m-1 步，走到整个区间的前驱结点处
  18.     for(let i=0;i<m-1;i++){
  19.         p = p.next
  20.     }
  21.     // 缓存这个前驱结点到 leftHead 里
  22.     leftHead = p
  23.     // start 是反转区间的第一个结点
  24.     let start = leftHead.next  
  25.     // pre 指向start
  26.     pre = start
  27.     // cur 指向 start 的下一个结点
  28.     cur = pre.next
  29.     // 开始重复反转动作
  30.     for(let i=m;i<n;i++){
  31.         let next = cur.next
  32.         cur.next = pre
  33.         pre = cur
  34.         cur = next
  35.     }
  36.     //  leftHead 的后继结点此时为反转后的区间的第一个结点
  37.     leftHead.next = pre
  38.     // 将区间内反转后的最后一个结点 next 指向 cur
  39.     start.next=cur
  40.     // dummy.next 永远指向链表头结点
  41.     return dummy.next
  42. };