LeetCode 25. K 个一组翻转链表

◎

本节目标

先确认完整分组，再原地翻转半开区间并连接前后边界。

查看 LeetCode 原题

题意与边界

从头开始每 k 个节点组成一组并原地翻转。最后不足 k 个节点的部分必须保持原顺序，不能通过交换节点值代替重连；题目保证 1 <= k <= n。

先确认边界再改指针

groupPrev 指向待处理组之前的节点。先从它出发走 k 步寻找 kth；若找不到，说明剩余不足一组，立即返回。保存 groupNext = kth.next 后，把当前组按半开区间 [groupPrev.next, groupNext) 反转，再连接组前驱、翻转后的组头和下一组入口。

正确性依据

每轮开始时，groupPrev 之前的完整组均已翻转并连接正确。只有确认 kth 存在后才修改当前组，所以不足一组的尾部从未被触碰。区间反转把恰好 k 个原节点次序颠倒，前后两次连接恢复整条链表连续性，随后不变量移动到下一组。

代码实现

C++

C++17

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0, head);
        ListNode* groupPrev = &dummy;
        while (true) {
            ListNode* kth = groupPrev;
            for (int i = 0; i < k && kth != nullptr; i++) {
                kth = kth->next;
            }
            if (kth == nullptr) {
                break;
            }

            ListNode* groupNext = kth->next;
            ListNode* prev = groupNext;
            ListNode* cur = groupPrev->next;
            while (cur != groupNext) {
                ListNode* next = cur->next;
                cur->next = prev;
                prev = cur;
                cur = next;
            }

            ListNode* oldHead = groupPrev->next;
            groupPrev->next = kth;
            groupPrev = oldHead;
        }
        return dummy.next;
    }
};

Python

Python 3

from typing import Optional


class Solution:
    def reverseKGroup(
        self,
        head: Optional[ListNode],
        k: int,
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy
        while True:
            kth = group_prev
            for _ in range(k):
                kth = kth.next
                if kth is None:
                    return dummy.next

            group_next = kth.next
            prev = group_next
            cur = group_prev.next
            while cur is not group_next:
                next_node = cur.next
                cur.next = prev
                prev = cur
                cur = next_node

            old_head = group_prev.next
            group_prev.next = kth
            group_prev = old_head

复杂度分析

• 时间复杂度：O(n)，每个节点只参与常数次定位和重连。
• 空间复杂度：O(1)，使用迭代指针。

易错点

• 未确认组长就开始反转，导致不足一组的尾部也被改变。
• 反转时把 prev 初始化为空，丢失与下一组的连接。
• 完成一组后没有把 groupPrev 移到原组头。

模式迁移

复杂链表局部修改应先冻结边界，再操作半开区间，最后恢复两端连接。这个顺序可迁移到区间反转、分段重排和链表归并。