Reverse Nodes in k-Group

25. Reverse Nodes in k-Group

分析

引入虚拟头节点
- 创建一个虚拟头节点 dummy，使其 next 指向链表的头节点，以便统一处理头节点的翻转
遍历链表检查是否需要翻转
- 使用指针 cur 标记当前分组的前驱节点
- 检查 cur 后是否至少还有 k 个节点。如果节点数不足 k，直接退出循环
翻转当前分组的 k 个节点
- 记录当前分组的起点 a 和翻转后的起点 b
- 按照链表翻转的规则，通过调整指针完成当前分组内的节点翻转，循环 k-1 次
连接翻转后的链表
- 让当前分组的前驱节点 cur->next 指向翻转后的新头节点 a
- 让当前分组的尾节点连接到下一分组的起始节点 b
- 更新 cur 为当前分组的尾节点

时间复杂度

每个节点最多被访问两次（检查和翻转），时间复杂度 O(n)

空间复杂度

空间复杂度 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


class Solution
{
public:
    ListNode* reverseKGroup(ListNode* head, int k)
    {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        ListNode* cur = dummy;

        while (true)
        {
            // 检查是否有足够的节点进行翻转
            ListNode* check = cur;
            for (int i = 0; i < k && check; ++i)
                check = check->next;
            if (!check)
                break;

            // 翻转当前分组的 k 个节点
            ListNode *a = cur->next, *b = cur->next->next;
            for (int i = 0; i < k - 1; ++i)
            {
                ListNode* c = b->next; // 暂存下一节点
                b->next = a;          // 翻转当前节点
                a = b;                // 同时后移
                b = c;
            }

            // 连接翻转后的链表
            ListNode* c = cur->next;
            cur->next = a;   // 当前分组的前驱节点指向翻转后的新头节点
            c->next = b;     // 当前分组的尾节点连接到下一分组的起始节点
            cur = c;         //  更新 cur 为当前分组的尾节点
        }

        // 返回结果链表
        return dummy->next;
    }
};