25. K 个一组翻转链表

难度：🔴 Hard | 标签：链表 | 状态：⬜ LeetCode 链接

思路

分段反转。每次先数 k 个节点，够才反转；不够保持原样。 dummy + groupPrev 锚定每段前驱。

代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummy(0, head), *gPrev = &dummy;
        while (true) {
            ListNode* kth = gPrev;
            for (int i = 0; i < k && kth; ++i) kth = kth->next;
            if (!kth) break;
            ListNode *groupNext = kth->next;
            // reverse [gPrev->next, kth]
            ListNode *prev = groupNext, *cur = gPrev->next;
            while (cur != groupNext) {
                ListNode* nxt = cur->next;
                cur->next = prev;
                prev = cur;
                cur = nxt;
            }
            ListNode *tmp = gPrev->next;
            gPrev->next = kth;
            gPrev = tmp;
        }
        return dummy.next;
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 不够 k 个时不反转，直接 break
• 反转范围用 prev = groupNext 初始化，省去断尾步骤
• gPrev 跳到本组反转后的尾（即原来的头）