25. K 个一组翻转链表

leetcode
2.1k words

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/

解答：

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
class Solution {
protected:
    pair<ListNode*, ListNode*> _Reverse(ListNode* head, ListNode* tail) {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* nxt = nullptr;
        ListNode* right = tail->next;
        while (cur&&cur!=right) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return { tail,head };
    }
public:
    ListNode* reverseKGroup(ListNode* head, int k) {  
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode*tail=dummy;
        ListNode* pre = dummy, * nxt = nullptr;
        while (head) {
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (tail == nullptr) { return dummy->next; }
            }
            nxt = tail->next;
            pair<ListNode*, ListNode*> res = _Reverse(head,tail);
            head = res.first;
            tail = res.second;
            pre->next = head;
            tail->next = nxt;
            pre = tail;
            head = nxt;
        }
        return dummy->next;
    }
};

解释：

主函数 reverseKGroup

1
2
3
4
5
if (!head) { return nullptr; }
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
ListNode* tail = nullptr;

首先，检查输入链表是否为空。接着，创建一个哑节点 dummy，它的 next 指针指向头节点 head。这样做是为了简化在头节点前进行操作的逻辑。pre 指针初始化为指向 dummy，tail 指针用于遍历。

1
2
3
4
5
6
7
8
9
while (head) {
    tail = pre;
    for (int i = 0; i < k; ++i) {
        tail = tail->next;
        if (tail == nullptr) {
            return dummy->next;
        }
    }
    ListNode* nex = tail->next;

在主循环中，尝试找到每组的最后一个节点 tail。如果在尝试移动 k 次到达 tail 节点的过程中发现 tail 为 nullptr（即这一组的节点数少于 k），则返回已经翻转的链表部分。nex 存储了当前组翻转部分的下一个节点，用于之后重新连接链表。

1
2
3
4
5
6
7
pair<ListNode*, ListNode*> result = Reverse(head, tail);
head = result.first;
tail = result.second;
pre->next = head;
tail->next = nex;
pre = tail;
head = nex;

调用 Reverse 函数翻转当前组的节点，然后重新连接翻转后的链表片段。更新 pre 和 head，为处理下一组做准备。

辅助函数 Reverse

1
2
3
4
5
6
7
8
9
10
ListNode* pre = tail->next;
ListNode* cur = head;
ListNode* temp = nullptr;
while (pre != tail) {
    temp = cur->next;
    cur->next = pre;
    pre = cur;
    cur = temp;
}
return { tail, head };

在 Reverse 函数中，通过循环将每个节点的 next 指针指向它的前一个节点，从而实现链表的翻转。注意，翻转结束后，原链表的 head 成为新链表的尾节点，原 tail 成为新链表的头节点。因此，函数返回这一对节点以便重新连接链表。

最终返回

1
return dummy->next;

最后，返回哑节点 dummy 的下一个节点，即翻转后链表的头节点。

通过以上步骤，该算法实现了链表中每 k 个节点一组进行翻转的要求，同时保持了不足 k 个节点的组原样。这种方法利用哑节点简化了操作，并通过在原链表上直接修改指针的方式避免了使用额外空间。

Comments