25 K 个一组翻转链表

一、题目

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

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

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

![](/leetcode/assets/25.K 个一组翻转链表.png)

二、题解

方法一：迭代 + 原地翻转

思路：链表模拟、双指针、分组翻转。

1. 核心思路

题目要求每 k 个节点为一组进行翻转，因此可以从链表头部开始，不断寻找长度为 k 的分组。

对于每一组节点：

  • 先找到这一组的第 k 个节点；
  • 如果剩余节点不足 k 个，直接结束；
  • 如果剩余节点达到 k 个，就将这一组原地翻转；
  • 翻转后重新连接上一组、当前组和下一组。

为了方便处理第一组翻转后头节点发生变化的情况，创建虚拟头节点 dummy。

定义以下几个重要指针：

pre：当前分组前面的一个节点
groupHead：当前分组的第一个节点
tail：当前分组的第 k 个节点
nextGroup：下一组的第一个节点

例如：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
   ↑      ↑    ↑    ↑
  pre  group  tail nextGroup
        Head

当 k = 2 时，翻转第一组后：

dummy -> 2 -> 1 -> 3 -> 4 -> 5
              ↑
             pre

原来的 groupHead 在翻转后变成当前组的尾节点，因此下一轮需要令：

pre = groupHead;

2. 具体步骤

  1. 创建虚拟头节点 dummy，令 dummy.next = head。
  2. 使用 pre 指向当前待翻转分组的前一个节点。
  3. 从 pre 开始向后寻找第 k 个节点 tail。
  4. 如果在寻找过程中遇到 null，说明剩余节点不足 k 个，直接返回结果。
  5. 记录当前分组的第一个节点 groupHead = pre.next。
  6. 记录下一组的第一个节点 nextGroup = tail.next。
  7. 翻转 [groupHead, tail] 范围内的所有节点。
  8. 将 pre.next 指向翻转后的头节点 tail。
  9. 将 pre 移动到翻转后的尾节点 groupHead。
  10. 继续处理下一组，直到剩余节点不足 k 个。

3. 关键逻辑

首先寻找当前分组的第 k 个节点：

ListNode tail = pre;

for (int i = 0; i < k; i++) {
    tail = tail.next;

    if (tail == null) {
        return dummy.next;
    }
}

解释：

  • tail 从 pre 开始向后移动 k 次；
  • 如果移动过程中 tail == null，说明剩余节点不足 k 个；
  • 根据题目要求，不足 k 个的节点保持原有顺序，因此直接返回结果。

翻转当前分组：

ListNode groupHead = pre.next;
ListNode nextGroup = tail.next;

ListNode prev = nextGroup;
ListNode cur = groupHead;

while (cur != nextGroup) {
    ListNode next = cur.next;

    cur.next = prev;
    prev = cur;
    cur = next;
}

解释：

  • groupHead 是当前组的第一个节点；
  • tail 是当前组的最后一个节点；
  • nextGroup 是下一组的第一个节点；
  • 将 prev 初始化为 nextGroup，可以让当前组翻转后自动连接到下一组；
  • 当 cur == nextGroup 时，说明当前组的所有节点都已经翻转完成。

重新连接链表：

pre.next = tail;
pre = groupHead;

解释：

  • tail 原来是当前组的最后一个节点，翻转后变成当前组的第一个节点；
  • groupHead 原来是当前组的第一个节点，翻转后变成当前组的最后一个节点；
  • 因此让 pre.next 指向 tail；
  • 再让 pre 移动到 groupHead，继续处理下一组。

4. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *
 *     ListNode() {}
 *
 *     ListNode(int val) {
 *         this.val = val;
 *     }
 *
 *     ListNode(int val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. 创建虚拟头节点，方便处理第一组翻转
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        // pre 指向当前待翻转分组的前一个节点
        ListNode pre = dummy;

        while (true) {
            // 2. 寻找当前分组的第 k 个节点
            ListNode tail = pre;

            for (int i = 0; i < k; i++) {
                tail = tail.next;

                // 剩余节点不足 k 个，不进行翻转
                if (tail == null) {
                    return dummy.next;
                }
            }

            // 3. 记录当前分组的第一个节点
            ListNode groupHead = pre.next;

            // 记录下一组的第一个节点
            ListNode nextGroup = tail.next;

            // 4. 原地翻转当前分组
            // prev 从 nextGroup 开始，使翻转后的尾节点直接连接下一组
            ListNode prev = nextGroup;
            ListNode cur = groupHead;

            while (cur != nextGroup) {
                // 暂存当前节点的下一个节点
                ListNode next = cur.next;

                // 修改当前节点的 next 指针
                cur.next = prev;

                // 指针向后移动
                prev = cur;
                cur = next;
            }

            // 5. 连接上一组和当前组
            // tail 翻转后成为当前组的头节点
            pre.next = tail;

            // groupHead 翻转后成为当前组的尾节点
            // 下一轮从它的后面继续处理
            pre = groupHead;
        }
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点会在寻找分组和翻转分组时被访问有限次，因此总时间复杂度为 O(n)O(n)。

空间复杂度：O(1)O(1)

说明：只使用了若干链表指针，没有使用与链表长度相关的额外空间。

方法二：递归 + 分组翻转

思路：递归、链表原地翻转。

1. 核心思路

方法一使用循环逐组翻转，而方法二可以通过递归处理每一个长度为 k 的分组。

对于当前链表：

  • 先检查从 head 开始是否至少还有 k 个节点；
  • 如果不足 k 个节点，直接返回 head，保持原有顺序；
  • 如果达到 k 个节点，就翻转当前的前 k 个节点；
  • 然后递归处理剩余链表；
  • 最后将当前组的尾节点连接到递归处理后的链表头部。

例如：

1 -> 2 -> 3 -> 4 -> 5，k = 2

先翻转当前组：

2 -> 1

剩余部分：

3 -> 4 -> 5

递归处理剩余部分：

4 -> 3 -> 5

最后连接：

2 -> 1 -> 4 -> 3 -> 5

2. 具体步骤

  1. 使用指针 check 从 head 开始向后移动 k 次。
  2. 如果移动过程中遇到 null，说明剩余节点不足 k 个，直接返回 head。
  3. 定义 prev 和 cur，翻转当前的前 k 个节点。
  4. 翻转结束后，prev 指向当前组的新头节点。
  5. head 原来是当前组的第一个节点，翻转后变成当前组的最后一个节点。
  6. cur 指向下一组的第一个节点。
  7. 递归调用 reverseKGroup(cur, k) 处理后面的链表。
  8. 令 head.next 指向递归处理后的链表头节点。
  9. 返回当前组翻转后的头节点 prev。

3. 关键逻辑

检查剩余节点是否达到 k 个：

ListNode check = head;

for (int i = 0; i < k; i++) {
    if (check == null) {
        return head;
    }

    check = check.next;
}

解释：

  • check 向后移动 k 次；
  • 如果移动过程中出现 null，说明剩余节点不足 k 个；
  • 不足 k 个的节点不能翻转，因此直接返回当前头节点 head。

翻转当前的前 k 个节点：

ListNode prev = null;
ListNode cur = head;

for (int i = 0; i < k; i++) {
    ListNode next = cur.next;

    cur.next = prev;
    prev = cur;
    cur = next;
}

解释：

  • prev 指向已经翻转完成的链表；
  • cur 指向当前需要处理的节点；
  • next 暂存后面的链表，防止修改 cur.next 后丢失；
  • 循环执行 k 次后，当前组翻转完成。

递归处理下一组：

head.next = reverseKGroup(cur, k);
return prev;

解释：

  • head 原来是当前组的第一个节点；
  • 翻转后，head 变成当前组的最后一个节点；
  • cur 指向下一组的第一个节点；
  • 递归处理下一组，再让 head.next 指向递归结果；
  • prev 是当前组翻转后的头节点，因此返回 prev。

4. 代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *
 *     ListNode() {}
 *
 *     ListNode(int val) {
 *         this.val = val;
 *     }
 *
 *     ListNode(int val, ListNode next) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 1. 检查剩余节点是否达到 k 个
        ListNode check = head;

        for (int i = 0; i < k; i++) {
            // 剩余节点不足 k 个，保持原有顺序
            if (check == null) {
                return head;
            }

            check = check.next;
        }

        // 2. 翻转当前的前 k 个节点
        ListNode prev = null;
        ListNode cur = head;

        for (int i = 0; i < k; i++) {
            // 暂存当前节点的下一个节点
            ListNode next = cur.next;

            // 修改当前节点的 next 指针
            cur.next = prev;

            // 指针向后移动
            prev = cur;
            cur = next;
        }

        /*
         * 3. 递归处理剩余链表
         *
         * head 原来是当前组的第一个节点，
         * 翻转后变成当前组的最后一个节点。
         *
         * cur 指向下一组的第一个节点。
         */
        head.next = reverseKGroup(cur, k);

        // prev 是当前组翻转后的头节点
        return prev;
    }
}

5. 复杂度分析

时间复杂度：O(n)O(n)

说明：每个节点只会被检查和翻转有限次，因此总时间复杂度为 O(n)O(n)。

空间复杂度：O(n/k)O(n / k)

说明：每处理一组节点会产生一次递归调用，递归深度大约为 n/kn / k，额外空间主要来自递归调用栈。

评论