No.25 K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

解题思路

实现

方法一

题意是以 k 个节点为一组进行反转，返回反转后的链表， 从左到右扫描一遍链表，扫描过程中，以 k 为单位把数组分为若干段，对每一段进行反转。给定首尾节点，如何对链表进行翻转？ 链表的解析过程，初始化一个为 null 的前置节点 prev，然后遍历链表的同时，当前节点 current 的下一个指向前置节点，在改变当前节点的指向前，用临时变量保存当前节点的下一个节点 current.next。

let temp = current.next;
current.next = prev;
prev = current;
current = temp;

举例如图：翻转整个链表 1->2->3->4->null=> 4->3->2->1->null

这里对每一组 k 个节点进行翻转。

1. 先分组，用一个 count 变量记录当前节点个数
2. 用一个 start 变量记录当前分组的起始节点位置的前一个节点
3. 用一个 end 变量记录要翻转的最后一个节点位置
4. 翻转一组 k 个节点，即：(start, end) - start and end exclusively
5. 翻转后，start 指向反转后链表，区间 (start, end) 中最后一个节点，返回 start 节点
6. 如果不需要翻转，end 就放后移动一次 end = end.next，每一次移动，都要 count + 1。 如图所示，步骤 4 和 5：翻转链表区间 (start, end)

举例如图，head=[1,2,3,4,5,6,7,8], k=3

注意：一般情况下对链表的操作，都有可能会引入一个新的 dummy 节点，因为 head 有可能会改变。这里 head 从 1->3，dummy(List(0)) 保持不变。

• 复杂度分析
  • 时间复杂度：O(n)
  • 空间复杂度：O(1)
• 关键点分析
  • 创建一个 dummy 节点
  • 对链表以 k 为单位进行分组，记录每一组的起始和最终节点位置
  • 对每一组进行翻转，更新起始和最后位置
  • 返回 dummy.next

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  // 翻转 start -> end 链表
  function reverseList(start, end) {
    let prev = start;
    let current = start.next;
    const node = current;
    while (current !== end) {
      let next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }
    start.next = prev;
    node.next = current;
    return node;
  }

  let dummy = new ListNode();
  dummy.next = head;
  let start = dummy;
  let end = dummy.next;
  let count = 0;

  while (end) {
    count++;
    if (count % k === 0) {
      start = reverseList(start, end.next);
      end = start.next;
    } else {
      // 移动指针
      end = end.next;
    }
  }

  return dummy.next;
};

方法二

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function (head, k) {
  let n = 0;
  let current = head;
  while (current) {
    n++;
    current = current.next;
  }

  const dummy = new ListNode(0, head);
  // p0 代表反转中间段的上一个节点
  // left = 1 时，构造哨兵节点
  // 循环后，到达反转后的上一个节点
  let p0 = dummy;
  let prev = null;
  current = p0.next;

  while (n >= k) {
    n -= k;
    for (let i = 0; i < k; i++) {
      const next = current.next;
      current.next = prev;
      prev = current;
      current = next;
    }

    // 保存原始 p0 的 next
    const next = p0.next;

    // p0 指向 prev
    // p0 的 next 指向 current
    p0.next.next = current;
    p0.next = prev;
    p0 = next;
  }
  return dummy.next;
};

:::callout 扩展 1

• 要求从后往前以 k 个为一组进行翻转，例：1->2->3->4->5->6->7->8, k=3，从后往前以 k=3 为一组。
  • 6->7->8 为一组翻转为 8->7->6
  • 3->4->5 为一组翻转为 5->4->3
  • 1->2 只有 2 个节点少于 k=3 个，不翻转
  • 最后返回 1->2->5->4->3->8->7->6
• 这里的思路跟从前往后以 k 个为一组进行翻转类似，可以进行预处理：
  • 翻转链表
  • 对翻转后的链表进行从前往后以 k 为一组翻转
  • 翻转上一步中得到的链表
• 例子：1->2->3->4->5->6->7->8, k = 3
  • 翻转链表得到：8->7->6->5->4->3->2->1
  • 以 k 为一组翻转：6->7->8->3->4->5->2->1
  • 翻转步骤 2 链表：1->2->5->4->3->8->7->6

:::