25. K 个一组翻转链表

实现思路

这题的核心是：每次先确认后面是否还有 k 个节点，够 k 个才反转，不够 k 个就保持原顺序。

使用一个 dummy 节点来简化边界情况的处理。
使用一个指针 prevGroupTail 来记录上一组的尾节点，初始指向 dummy。
每次循环先找到当前组的尾节点 currentGroupTail。如果不足 k 个节点，直接返回结果，不再反转。
记录当前组的头节点 currentGroupHead 和下一组的头节点 nextGroupHead，然后使用头插法反转当前组。
反转后，原来的组尾是新组头，原来的组头是新组尾：
- prevGroupTail.next 连接新组头 currentGroupTail；
- currentGroupHead.next 已经连接到 nextGroupHead；
- prevGroupTail 移动到 currentGroupHead，为下一轮做准备。

例如 1 → 2 → 3 → 4 → 5，k = 2 时，先反转 1 → 2 得到 2 → 1，再反转 3 → 4 得到 4 → 3，最后剩余的 5 不足 k 个，保持不变，结果为 2 → 1 → 4 → 3 → 5。

反转一组节点时的指针变化

反转时令 prev = nextGroupHead，这样当前组反转完成后，原来的组头会自然连接到下一组；cur 从当前组头开始，每次将 cur.next 指向 prev，再同时向后移动两个指针。

代码实现

var reverseKGroup = function (head, k) {
  const dummy = new ListNode(0, head);
  // 前一组的尾节点
  let prevGroupTail = dummy;

  while (true) {
    // 从上一组的尾节点开始向后移动 k 次，找到当前组的尾节点
    // 初始化时 currentGroupTail 与 prevGroupTail 指向同一位置，遍历后才指向当前组尾节点
    let currentGroupTail = prevGroupTail;
    for (let i = 0; i < k; i++) {
      currentGroupTail = currentGroupTail.next;
      // 如果剩余节点不足 k 个，则不需要反转，直接返回结果
      if (!currentGroupTail) return dummy.next;
    }

    // 记录当前组的头节点以及下一组的头节点
    let currentGroupHead = prevGroupTail.next;
    let nextGroupHead = currentGroupTail.next;

    // 反转当前组。prev 从下一组头开始，保证反转后当前组能接回后面的链表
    let prev = nextGroupHead;
    let cur = currentGroupHead;
    for (let j = 0; j < k; j++) {
      const temp = cur.next;
      cur.next = prev;
      prev = cur;
      cur = temp;
    }

    // 反转完成后，prev 与 currentGroupTail 指向同一个节点，都是当前组的新头
    // 这里使用语义更明确的 currentGroupTail，也可以写成 prevGroupTail.next = prev
    // 接回上一组：反转后 currentGroupTail 是当前组的新头
    prevGroupTail.next = currentGroupTail;

    // 反转后 currentGroupHead 是当前组的新尾，移动到这里继续处理下一组
    prevGroupTail = currentGroupHead;
  }
};

复杂度分析

时间复杂度：O(n)，每个节点至多被查找和反转一次。
空间复杂度：O(1)，只使用了常数个指针，没有额外创建节点。

边界情况

head 为空或只有一个节点时，直接返回原链表。
k = 1 时，每组只有一个节点，链表保持不变。
链表长度不是 k 的整数倍时，最后不足 k 个节点的部分保持原顺序。

ON THIS PAGE

#25. K 个一组翻转链表

#实现思路

#反转一组节点时的指针变化

#代码实现