25. K 个一组翻转链表

力扣题目链接 (opens new window)

题目描述

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

思路

本题是 24. 两两交换链表中的节点 的进阶版，从固定的两个一组，变成了 k 个一组。

核心思路

把链表分成多个长度为 k 的组，每组进行翻转，最后一组如果不足 k 个，保持原样。

步骤拆解

1. 判断剩余节点是否够 k 个：先遍历 k 个节点，如果不够就返回（不翻转）
2. 翻转当前这一组：翻转 k 个节点
3. 递归处理下一组：当前组翻转后，递归处理后面的部分
4. 连接各部分：把翻转后的组和后面的部分连接起来

翻转 k 个节点的逻辑

和翻转整个链表类似，用三个指针 prev、curr、next：

• prev 初始化为 null
• curr 从当前组的头节点开始
• 循环 k 次，每次把 curr 指向 prev，然后往后移动

翻转后：

• 原来的头节点变成尾节点
• 原来的尾节点变成头节点

连接逻辑

• 翻转前记录下一组的头节点
• 翻转后，当前组的尾节点（原头节点）连接到下一组翻转后的头节点
• 返回当前组翻转后的头节点（原尾节点）

虚拟头节点

用虚拟头节点简化边界处理。

模拟过程

以示例 2 为例，head = [1,2,3,4,5], k = 3：

原链表： 1 → 2 → 3 → 4 → 5

第一组（1,2,3）翻转：

• 翻转前：1 → 2 → 3
• 翻转后：3 → 2 → 1

第二组（4,5）不足 k=3，保持原样：

• 保持：4 → 5

连接：

• 3 → 2 → 1 → 4 → 5

解题代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (!head || k == 1) return head;
        
        // 检查剩余节点是否够 k 个
        ListNode* curr = head;
        for (int i = 0; i < k; i++) {
            if (!curr) return head; // 不足 k 个，保持原样
            curr = curr->next;
        }
        
        // 翻转前 k 个节点
        ListNode* prev = nullptr;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        // 递归翻转后面的部分，并连接
        head->next = reverseKGroup(curr, k);
        
        // 返回翻转后的头节点
        return prev;
    }
};

复杂度分析

• 时间复杂度：O(n)，每个节点访问常数次
• 空间复杂度：O(n/k)，递归栈的深度，共 n/k 组

其他语言

Python3

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or k == 1:
            return head
        
        # 检查剩余节点是否够 k 个
        curr = head
        for _ in range(k):
            if not curr:
                return head  # 不足 k 个，保持原样
            curr = curr.next
        
        # 翻转前 k 个节点
        prev = None
        curr = head
        for _ in range(k):
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node
        
        # 递归翻转后面的部分，并连接
        head.next = self.reverseKGroup(curr, k)
        
        # 返回翻转后的头节点
        return prev

Java

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k == 1) return head;
        
        // 检查剩余节点是否够 k 个
        ListNode curr = head;
        for (int i = 0; i < k; i++) {
            if (curr == null) return head;
            curr = curr.next;
        }
        
        // 翻转前 k 个节点
        ListNode prev = null;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // 递归翻转后面的部分，并连接
        head.next = reverseKGroup(curr, k);
        
        // 返回翻转后的头节点
        return prev;
    }
}

Go

func reverseKGroup(head *ListNode, k int) *ListNode {
    if head == nil || k == 1 {
        return head
    }
    
    // 检查剩余节点是否够 k 个
    curr := head
    for i := 0; i < k; i++ {
        if curr == nil {
            return head
        }
        curr = curr.Next
    }
    
    // 翻转前 k 个节点
    var prev *ListNode
    curr = head
    for i := 0; i < k; i++ {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }
    
    // 递归翻转后面的部分，并连接
    head.Next = reverseKGroup(curr, k)
    
    // 返回翻转后的头节点
    return prev
}

JavaScript

var reverseKGroup = function(head, k) {
    if (!head || k === 1) return head;
    
    // 检查剩余节点是否够 k 个
    let curr = head;
    for (let i = 0; i < k; i++) {
        if (!curr) return head;
        curr = curr.next;
    }
    
    // 翻转前 k 个节点
    let prev = null;
    curr = head;
    for (let i = 0; i < k; i++) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    // 递归翻转后面的部分，并连接
    head.next = reverseKGroup(curr, k);
    
    // 返回翻转后的头节点
    return prev;
};

迭代解法

递归解法简洁，但空间复杂度O(n/k)。如果要实现O(1)空间的迭代解法：

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prevGroup = dummy; // 上一组的尾节点
        
        while (true) {
            // 检查剩余节点是否够 k 个
            ListNode* kthNode = prevGroup;
            for (int i = 0; i < k; i++) {
                kthNode = kthNode->next;
                if (!kthNode) return dummy->next; // 不够 k 个，结束
            }
            
            // 记录下一组的头节点
            ListNode* nextGroup = kthNode->next;
            
            // 翻转当前组
            ListNode* prev = nextGroup;
            ListNode* curr = prevGroup->next;
            for (int i = 0; i < k; i++) {
                ListNode* next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = next;
            }
            
            // 连接
            ListNode* temp = prevGroup->next; // 当前组翻转前的头节点
            prevGroup->next = kthNode; // 上一组连接到当前组翻转后的头节点
            prevGroup = temp; // 更新 prevGroup 为当前组翻转后的尾节点
        }
        
        return dummy->next;
    }
};

与代码随想录联系

本题是链表翻转的综合应用，结合了：

• 206. 反转链表 — 基础的链表翻转
• 24. 两两交换链表中的节点 — k=2 的特例

在代码随想录的链表章节中，详细讲解了链表操作的核心技巧：

• 虚拟头节点：简化边界处理
• 多指针操作：prev、curr、next 三指针翻转
• 递归 vs 迭代：递归更简洁，迭代更省空间

本题的难点：

1. 如何判断剩余节点是否够 k 个
2. 翻转后如何连接各部分
3. 边界情况的处理

录友们如果对链表操作还不熟练，建议先做基础的翻转题，再来挑战本题。

链表题的核心是画图模拟，把指针的指向画清楚，代码就自然而然写出来了。