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

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

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

链表删除问题中，若走两次遍历，我们做了两件事：
1.求长度
2.做减法，找定位。
若用快慢指针，我们其实是把做减法和找定位这个过程给融合了。通过快指针先行一步、接着快慢指针一起前进这个操作，巧妙地把两个指针之间的差值保持在了“n”上（用空间换时间，本质上其实就是对关键信息进行提前记忆，这里咱们相当于用两个指针对差值实现了记忆），这样当快指针走到链表末尾（第 len 个）时，慢指针刚好就在 len - n 这个地方稳稳落地。

  1. /**
  2.  * @param {ListNode} head
  3.  * @param {number} n
  4.  * @return {ListNode}
  5.  */
  6. const removeNthFromEnd = function(head, n) {
  7.     // 初始化 dummy 结点
  8.     const dummy = new ListNode()
  9.     // dummy指向头结点
  10.     dummy.next = head
  11.     // 初始化快慢指针，均指向dummy
  12.     let fast = dummy
  13.     let slow = dummy
  15.     // 快指针闷头走 n 步
  16.     while(n!==0){
  17.         fast = fast.next
  18.         n--
  19.     }
  21.     // 快慢指针一起走
  22.     while(fast.next){
  23.         fast = fast.next
  24.         slow = slow.next
  25.     }
  27.     // 慢指针删除自己的后继结点
  28.     slow.next = slow.next.next
  29.     // 返回头结点
  30.     return dummy.next
  31. };

多指针法——链表的反转

完全反转一个链表

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

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

  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. };

局部反转一个链表

真题描述：反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明: 1 ≤ m ≤ n ≤ 链表长度。

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

输出: 1->4->3->2->5->NULL

  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. };