LeetCode题解：25. K 个一组翻转链表，迭代，JavaScript，详细注释

[chencl1986]

原题链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

解题思路：

可以先参考官方题解，再看本题解。

总体思路如下：

1. 将链表拆分成N个子链表，每个子链表有K个节点。
2. 单独翻转每个子链表。
3. 将翻转后的子链表与前后节点连接起来。
4. 需要注意判断链表为null，以及链表节点总数不是 k 的整数倍的情况。

如果说一次写出完整代码比较困难，我们可以分步骤解题：

1. 写出循环链表方法

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  // 反转子链表的方法，在 206. 反转链表 的基础上做改造，可以参考如下题解：
  // https://leetcode-cn.com/problems/reverse-linked-list/solution/206-fan-zhuan-lian-biao-javascriptwhilexun-huan-di/
  function reverseNode(head, tail) {
    // 待第2步补充
  }

  // 创建dummy节点，将其作为第一次遍历链表时的prevNode
  // dummyNode不会参与链表遍历，也就是说它的next指向始终是链表的头结点
  let dummyNode = new ListNode(-1);
  dummyNode.next = head;
  // 将dummyNode赋值给prevNode进入链表的遍历。
  // prevNode在遍历时，会不断移动。
  // 在第一次遍历时，prevNode.next会指向翻转后的链表头节点。
  // 此时dummyNode.next的指向也会同时被改变。
  let prevNode = dummyNode;

  while (head) {
    // 创建一个尾节点，它会被移动k位，最终指向当前子链表的伪节点。。
    let tail = prevNode;

    // 移动tail到当前子链表的尾部，同时判断剩余节点的长度是否>=k
    for (let i = 0; i < k; i++) {
      // 待第3步补充
    }

    // nextNode即为下一段子链表的头节点
    let nextNode = tail.next;

    // 将子链表反转，返回其新的头尾节点，用于连接符链表
    [head, tail] = reverseNode(head, tail);

    // 将父链表与子链表链接
    prevNode.next = head;
    tail.next = nextNode;

    // 向前移动prevNode和head，继续下一个子链表的循环
    prevNode = tail;
    head = tail.next;
  }

  // dummyNode的指向是链表的头节点，输出dummyNode.next就是将翻转后的链表输出。
  // 如果head为null，则不户进入while循环，而是直接被返回
  return dummyNode.next;
};

2. 增加反转子链表方法

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  // 反转子链表的方法，在 206. 反转链表 的基础上做改造，可以参考如下题解：
  // https://leetcode-cn.com/problems/reverse-linked-list/solution/206-fan-zhuan-lian-biao-javascriptwhilexun-huan-di/
  function reverseNode(head, tail) {
    // 如果子链表已经反转，那个反转之后的签一个节点，即为当前子链表的下一个节点。
    // 因此直接把签一个节点设置为tail.next
    let prevNode = tail.next;
    // 缓存head，使用node遍历子链表并进行反转。
    // 因为head指针不能改变，需要用于返回反转后的尾结点。
    let node = head;

    // 进行链表反转操作，prevNode不断移动，移动到tail时，表示该子链表反转完成。
    while (prevNode !== tail) {
      const tempNode = node.next;

      node.next = prevNode;
      prevNode = node;

      node = tempNode;
    }

    // 完成反转后，原来的头尾节点已经对调，则反过来返回。
    // 要注意这里，头尾节点其实都没有改变，只是他们的位置因为子链表被反转而调换了。
    return [tail, head];
  }

  // 创建dummy节点，将其作为第一次遍历链表时的prevNode
  // dummyNode不会参与链表遍历，也就是说它的next指向始终是链表的头结点
  let dummyNode = new ListNode(-1);
  dummyNode.next = head;
  // 将dummyNode赋值给prevNode进入链表的遍历。
  // prevNode在遍历时，会不断移动。
  // 在第一次遍历时，prevNode.next会指向翻转后的链表头节点。
  // 此时dummyNode.next的指向也会同时被改变。
  let prevNode = dummyNode;

  while (head) {
    // 创建一个尾节点，它会被移动k位，最终指向当前子链表的伪节点。。
    let tail = prevNode;

    // 移动tail到当前子链表的尾部，同时判断剩余节点的长度是否>=k
    for (let i = 0; i < k; i++) {
      // 待第3步补充
    }

    // nextNode即为下一段子链表的头节点
    let nextNode = tail.next;

    // 将子链表反转，返回其新的头尾节点，用于连接符链表
    [head, tail] = reverseNode(head, tail);

    // 将父链表与子链表链接
    prevNode.next = head;
    tail.next = nextNode;

    // 向前移动prevNode和head，继续下一个子链表的循环
    prevNode = tail;
    head = tail.next;
  }

  // dummyNode的指向是链表的头节点，输出dummyNode.next就是将翻转后的链表输出。
  // 如果head为null，则不户进入while循环，而是直接被返回
  return dummyNode.next;
};

3. 判断剩余节点的长度是否>=k

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  // 反转子链表的方法，在 206. 反转链表 的基础上做改造，可以参考如下题解：
  // https://leetcode-cn.com/problems/reverse-linked-list/solution/206-fan-zhuan-lian-biao-javascriptwhilexun-huan-di/
  function reverseNode(head, tail) {
    // 如果子链表已经反转，那个反转之后的签一个节点，即为当前子链表的下一个节点。
    // 因此直接把签一个节点设置为tail.next
    let prevNode = tail.next;
    // 缓存head，使用node遍历子链表并进行反转。
    // 因为head指针不能改变，需要用于返回反转后的尾结点。
    let node = head;

    // 进行链表反转操作，prevNode不断移动，移动到tail时，表示该子链表反转完成。
    while (prevNode !== tail) {
      const tempNode = node.next;

      node.next = prevNode;
      prevNode = node;

      node = tempNode;
    }

    // 完成反转后，原来的头尾节点已经对调，则反过来返回。
    // 要注意这里，头尾节点其实都没有改变，只是他们的位置因为子链表被反转而调换了。
    return [tail, head];
  }

  // 创建dummy节点，将其作为第一次遍历链表时的prevNode
  // dummyNode不会参与链表遍历，也就是说它的next指向始终是链表的头结点
  let dummyNode = new ListNode(-1);
  dummyNode.next = head;
  // 将dummyNode赋值给prevNode进入链表的遍历。
  // prevNode在遍历时，会不断移动。
  // 在第一次遍历时，prevNode.next会指向翻转后的链表头节点。
  // 此时dummyNode.next的指向也会同时被改变。
  let prevNode = dummyNode;

  while (head) {
    // 创建一个尾节点，它会被移动k位，最终指向当前子链表的伪节点。。
    let tail = prevNode;

    // 移动tail到当前子链表的尾部，同时判断剩余节点的长度是否>=k
    for (let i = 0; i < k; i++) {
      // 向后移动tail指针
      // 注意这里要先移动，再进行是否为空的判断，否则会报错
      tail = tail.next;

      // 如果tail为null，说明链表剩余部分不足k个，无需继续反转，直接返回结果
      if (!tail) {
        return dummyNode.next;
      }
    }

    // nextNode即为下一段子链表的头节点
    let nextNode = tail.next;

    // 将子链表反转，返回其新的头尾节点，用于连接符链表
    [head, tail] = reverseNode(head, tail);

    // 将父链表与子链表链接
    prevNode.next = head;
    tail.next = nextNode;

    // 向前移动prevNode和head，继续下一个子链表的循环
    prevNode = tail;
    head = tail.next;
  }

  // dummyNode的指向是链表的头节点，输出dummyNode.next就是将翻转后的链表输出。
  // 如果head为null，则不户进入while循环，而是直接被返回
  return dummyNode.next;
};