Eric 的小站

1
输入：head = [1,2,3,4,5], k = 2
2
输出：[2,1,4,3,5]

1
输入：head = [1,2,3,4,5], k = 3
2
输出：[3,2,1,4,5]

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* reverseKGroup(ListNode* head, int k) {
14
        ListNode* result = new ListNode();
15
        ListNode* p = head;
16
        ListNode* q = result;
17
        int ListLen = 0, count = 0;
18
        while (p) {
19
            ListLen++;
20
            p = p->next;
21
        }
22
        p = head;
23
        stack<int> stk;
24
        while (p) {
25
            int time = k;
26
            while (time--) {
27
                stk.push(p->val);
28
                p = p->next;
29
            }
30
            time = k;
31
            while (time--) {
32
                q->next = new ListNode(stk.top());
33
                q = q->next;
34
                stk.pop();
35
                count++;
36
            }
37
            if (ListLen - count < k)
38
                break;
39
        }
40
        q->next = p;
41
        return result->next;
42
    }
43
};

1
class Solution {
2
public:
3
    // 翻转一个子链表，并且返回新的头与尾
4
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
5
        ListNode* prev = tail->next;
6
        ListNode* p = head;
7
        while (prev != tail) {
8
            ListNode* nex = p->next;
9
            p->next = prev;
10
            prev = p;
11
            p = nex;
12
        }
13
        return {tail, head};
14
    }
15

16
    ListNode* reverseKGroup(ListNode* head, int k) {
17
        ListNode* hair = new ListNode(0);
18
        hair->next = head;
19
        ListNode* pre = hair;
20

21
        while (head) {
22
            ListNode* tail = pre;
23
            // 查看剩余部分长度是否大于等于 k
24
            for (int i = 0; i < k; ++i) {
25
                tail = tail->next;
26
                if (!tail) {
27
                    return hair->next;
28
                }
29
            }
30
            ListNode* nex = tail->next;
31
            // 这里是 C++17 的写法，也可以写成
32
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
33
            // head = result.first;
34
            // tail = result.second;
35
            tie(head, tail) = myReverse(head, tail);
36
            // 把子链表重新接回原链表
37
            pre->next = head;
38
            tail->next = nex;
39
            pre = tail;
40
            head = tail->next;
41
        }
42

43
        return hair->next;
44
    }
45
};
46

47
作者：力扣官方题解
48
链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/solutions/248591/k-ge-yi-zu-fan-zhuan-lian-biao-by-leetcode-solutio/
49
来源：力扣（LeetCode）
50
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。