算法

K 个一组翻转链表

loser

23 Aug 2026 • 9 min read

给你链表的头节点 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) 额外内存空间的算法解决此问题吗？

解法一（递归）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        // 检查剩余节点是否够 k 个，不够则保持原样
        ListNode* tail = head;
        for (int i = 0; i < k; ++i)
        {
            if (tail == nullptr)
            {
                return head;
            }
            tail = tail->next;
        }

        // 反转当前这 k 个节点
        ListNode* prev = nullptr;
        ListNode* cur = head;
        for (int i = 0; i < k; ++i)
        {
            ListNode* nxt = cur->next;
            cur->next = prev;
            prev = cur;
            cur = nxt;
        }

        // 反转后，head 成为本组的尾节点，cur 指向下一组的头节点
        head->next = reverseKGroup(cur, k);

        return prev;
    }
};

解法二（迭代）：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy;

        while (prev->next != nullptr)
        {
            // 找到当前这组 k 个节点的尾节点
            ListNode* tail = prev;
            for (int i = 0; i < k; ++i)
            {
                tail = tail->next;
                if (tail == nullptr)
                {
                    return dummy.next;
                }
            }

            // 记录下一组的头节点
            ListNode* nextGroup = tail->next;

            // 反转当前这一组 [prev->next, tail]
            ListNode* cur = prev->next;
            ListNode* groupHead = cur;
            ListNode* pre = nextGroup;
            while (cur != nextGroup)
            {
                ListNode* nxt = cur->next;
                cur->next = pre;
                pre = cur;
                cur = nxt;
            }

            // 前一个节点接上反转后的组头
            prev->next = pre;

            // prev 移动到本组反转后的尾节点，继续处理下一组
            prev = groupHead;
        }

        return dummy.next;
    }
};

核心思想

这题是「反转链表」的加强版，区别在于每次不是反转整条链表，而是反转连续的一段、每段恰好 k 个节点。

直接的想法是：

把链表按每 k 个节点切成若干段，对每一段做一次反转，再把它们按顺序接起来。

这题的难点主要有两个：

一段反转后，它原来的头节点变成了尾节点，原来的尾节点变成了头节点，前后的连接关系要重新接对。
最后剩余不足 k 个节点的那一段，必须保持原顺序，不能反转。

所以算法可以统一成「三件套」：先数够 k 个节点，再反转这一段，最后把这段接回链表。

递归解法把「数够 k 个 → 反转 → 接回」这三步写得很直观；迭代解法用一个虚拟头节点和几个指针，在 O(1) 额外空间内完成同样的事情，满足进阶要求。

解法一：递归

递归的思路非常直接。

对于当前以 head 开头的链表，先往后数 k 个节点，看够不够。

如果不够 k 个，说明这一段的长度不足 k，按题目要求保持原顺序，直接返回 head：

ListNode* tail = head;
for (int i = 0; i < k; ++i)
{
    if (tail == nullptr)
    {
        return head;
    }
    tail = tail->next;
}

如果够 k 个，就把前 k 个节点反转。

反转用的是经典的迭代反转写法：

ListNode* prev = nullptr;
ListNode* cur = head;
for (int i = 0; i < k; ++i)
{
    ListNode* nxt = cur->next;
    cur->next = prev;
    prev = cur;
    cur = nxt;
}

反转结束后：

prev 指向这一段反转后的新头节点。
head 变成了这一段反转后的尾节点。
cur 指向下一段的头节点。

剩下的问题就交给递归解决，把下一段接在当前这段的尾节点后面：

head->next = reverseKGroup(cur, k);

最后返回反转后的新头节点 prev。

解法二：迭代

迭代解法不借助递归调用栈，只用常数个指针，因此满足进阶要求的 O(1) 空间。

为了统一处理头节点和后续节点，先建一个虚拟头节点：

ListNode dummy(0, head);

prev 始终指向「当前这一组的前一个节点」。

每一轮循环做四件事。

1. 数够 `k` 个节点

从 prev 出发，往后走 k 步找到本组的尾节点 tail：

ListNode* tail = prev;
for (int i = 0; i < k; ++i)
{
    tail = tail->next;
    if (tail == nullptr)
    {
        return dummy.next;
    }
}

如果在中间就遇到 nullptr，说明剩余节点不足 k 个，直接返回整个链表。

2. 记录下一组的头节点

在反转前，先记下本组尾节点的下一个节点：

ListNode* nextGroup = tail->next;

反转后本组会断开，如果不先记下，后面的链表就找不到了。

3. 反转当前这一组

当前要反转的区间是 [prev->next, tail]。

反转时把 nextGroup 作为反转后的终点，让这段链表的尾节点接回下一组：

ListNode* cur = prev->next;
ListNode* groupHead = cur;
ListNode* pre = nextGroup;
while (cur != nextGroup)
{
    ListNode* nxt = cur->next;
    cur->next = pre;
    pre = cur;
    cur = nxt;
}

结束后：

pre 是本组反转后的新头节点。
groupHead（也就是原来的 prev->next）是本组反转后的尾节点。

4. 接回链表并移动到下一组

先把 prev 接上本组反转后的新头：

prev->next = pre;

再把 prev 移动到本组反转后的尾节点，也就是 groupHead，准备处理下一组：

prev = groupHead;

边界情况

如果链表节点总数正好是 k 的整数倍，例如：

head = [1,2,3,4], k = 2

每一组都能完整反转，结果是：

[2,1,4,3]

如果最后剩余不足 k 个节点，例如：

head = [1,2,3,4,5], k = 3

前 3 个节点反转成 [3,2,1]，最后剩下的 [4,5] 不足 3 个，保持原顺序，结果是：

[3,2,1,4,5]

如果 k == 1，每一组只有一个节点，反转后顺序不变，两种情况下的代码都能正确返回原链表。

如果 k == n，整条链表只分成一组，等价于反转整条链表。

正确性证明

我们证明：算法返回的链表，是把原链表每 k 个节点一组反转、不足 k 个的部分保持原顺序后的结果。

结论 1：每一组被反转的部分，反转结果正确

反转一段链表用的是经典的三指针迭代反转。

反转过程中，pre 始终保持「已经反转好的部分」的头节点。

每当处理节点 cur 时，先保存其后继：

ListNode* nxt = cur->next;

再让 cur 指向已经反转好的部分：

cur->next = pre;

然后 pre、cur 同时前进。

这样经过一组内所有节点后，这段链表的顺序被完全反转，并且没有丢失任何节点。

因此每一组的反转结果都正确。

结论 2：不足 `k` 个节点的部分保持原顺序

两种解法在反转前都会先数节点。

递归解法中，如果从 head 往后数不足 k 个就遇到 nullptr，直接返回原 head，不做任何修改。

迭代解法中，如果从 prev 往后数不足 k 个就遇到 nullptr，直接返回 dummy.next，此前已经处理好的部分保持不动，剩余部分也保持原顺序。

因此最后不足 k 个节点的部分不会被反转。

结论 3：各组之间连接正确，不会多算也不会漏算

递归解法中，反转后：

当前组的尾节点是原来的 head。
下一组的头节点是 cur。
通过 head->next = reverseKGroup(cur, k) 把下一组接在当前组后面。

迭代解法中，反转前记录了：

ListNode* nextGroup = tail->next;

反转后通过：

prev->next = pre;

把本组的新头接在上一组后面，同时本组的尾节点 groupHead 已经通过反转指向了 nextGroup。

两种解法都保证了：每一组恰好被处理一次，组与组之间不重复、不遗漏、不断链。

得出结论

由结论 1 可知，每个完整组都被正确反转。

由结论 2 可知，不足 k 个的部分保持原顺序。

由结论 3 可知，各组之间连接正确。

因此算法返回的链表满足题意，算法正确。

举例理解

以：

head = [1,2,3,4,5], k = 3

为例，看迭代解法的过程。

初始：

dummy -> 1 -> 2 -> 3 -> 4 -> 5
prev = dummy

第一轮，从 prev 往后数 3 个节点，得到 tail = 3，说明够 k 个。

记录 nextGroup = 4，然后反转区间 [1,2,3]：

反转后：3 -> 2 -> 1

接回链表：

dummy -> 3 -> 2 -> 1 -> 4 -> 5
prev = 1

第二轮，从 prev = 1 往后数 3 个节点：

数到 4，再往后就是 5，再往后是 null

中途遇到 nullptr，说明剩余 [4,5] 不足 3 个。

直接返回 dummy.next，得到：

[3,2,1,4,5]

可以看到，前 3 个节点被反转，最后的 [4,5] 保持原顺序，结果正确。

复杂度分析

解法一

递归处理过程中，每个节点被访问常数次。

时间复杂度：O(n)
空间复杂度：O(n)，递归调用栈深度约为 n / k 层

解法二

每个节点在数节点和反转两个阶段中都被访问常数次。

时间复杂度：O(n)
空间复杂度：O(1)，只使用了常数个指针

其中 n 是链表中的节点数。

迭代解法只用常数额外空间，是满足进阶要求 O(1) 空间的推荐解法。