开始之前

这两个的解法思路和反转链表其实差不多，所以放在一章一起解决

链表指定区间反转

之前写过整个链表的反转，主要做法就是

1. 下一个节点指针指向下一个节点

2. 当前节点的 next 属性指向上一个节点

3. 将上一个节点指针指向当前节点

4. 将当前节点指针移动到下一个节点指针指向的节点

描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转。

数据范围

链表长度 0 < size <= 1000

0 < m <=n < size

链表中每个节点的值满足 |val| <= 1000

要求

时间复杂度 O(n)，空间复杂度 O(n)

思路

先遍历到开始反转的位置，然后用之前的反转算法略微改造后去遍历。

代码

function reverseBetween(head, m, n) {
  // write code here
  if (m == n) {
    return head;
  }
  // 在head前再构造一个节点
  let realHead = new ListNode(0);
  realHead.next = head;
  // 分别设置两个指针指向前一个节点和当前节点
  let previous = realHead;
  let current = head;
  // 遍历前m-1个节点
  for (let i = 1; i < m; i++) {
    previous = previous.next;
  }
  // 记录第m个节点
  current = previous.next;
  for (let i = 0; i < n - m; i++) {
    // 记录上一节点指针指向节点的下一个节点
    let nextNode = previous.next;
    // 上一节点指针同步到当前节点指针指向的节点去
    previous.next = current.next;
    // 当前节点指针后移一个节点
    current.next = current.next.next;
    //
    previous.next.next = nextNode;
  }
  return realHead.next;
}

代码解读

代码首先是构造了一个节点指向了传入的头节点，并用 previous 指针指向了构造的节点

将 current 指针指向了头节点

这时候就可以用 previous 指针去遍历传入的链表，到 m-1 指定的节点。

使用 current 获取到 m 节点。

开始执行反转算法，这个反转算法和整体反转算法略有差异。

整体反转算法是，遍历到某个节点，记录它的 next，修改节点 next 指向 prev，prev 指向当前节点，当前节点移动到 next。

而这个算法就不是那么直观了。下面表格重点关注一下 next 指针

一开始节点是这样的

进入第一次循环,做了以下操作

let nextNode = previous.next;

previous.next = current.next;

current.next = current.next.next;

previous.next.next = nextNode;

可以看到，第一次循环结束，链表顺序是

m-2 m-1 m+1 m m+2 m+3 m+4

再来执行第二次循环。

let let nextNode = previous.next;

previous.next = current.next;

current.next = current.next.next;

previous.next.next = nextNode;

第二次循环结束时，链表为

m-2 m-1 m+2 m+1 m m+3 m+4

可以总结出，pnext 和 cnext 在每次循环中，后向后移动一位，p 和 c 不移动。

n 也随着 pnext 的移动而移动。

就是不断的 m-1 的 next 指向下一个未遍历的节点并反转。

同时将 m 的 next 指向未遍历且未反转的节点。

循环完成反转。

链表 K 个一组反转

写到这已经是凌晨 2:21 了，🐕 命要紧，睡觉了，明天起来补

描述

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表。

如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样。

你不能更改节点中的值，只能更改节点本身。

数据范围

0 <= n <= 2000 ， 1 <= k <= 2000。

链表中每个元素都满足 0 <= val <= 1000。

要求

空间复杂度 O(1)，时间复杂度 O(n)。

思路

就按照 k 个一组反转，然后递归调反转后续的链表即可。

代码

function reverseKGroup(head, k) {
  // write code here
  let pre = null;
  let current = head;
  let node = head;
  // 循环检查剩余节点是否有k个，没有直接返回
  for (let i = 0; i < k; i++) {
    if (node === null) {
      return head;
    }
    node = node.next;
  }
  // 反转前k个节点 并加入到链中
  for (let i = 0; i < k; i++) {
    // 记录下一个节点
    let temp = current.next;
    // 反转链表
    current.next = pre;
    // 获取到当前节点作为前一个节点，供下次循环使用
    pre = current;
    // 获取到下一个节点，供下次循环使用
    current = temp;
  }
  // 递归反转直到结束
  head.next = reverseKGroup(current, k);
  return pre;
}

代码解读

代码先对入参进行了一个检查，看剩余节点，这是递归的结束条件。

然后就是反转 k 个节点.

然后将剩余节点放入递归去反转。

比较简单。

小结

今晚刷刷 MDN 吧，算法刚不动了。