K个一组反转链表_k 个一组翻转链表

链表如下: head -> 1, tail -> 8
1 -> 2 -> 3 -> 4 ->5 -> 6 -> 7 -> 8-> nullptr

K = 3
=> 
1 -> 2 -> 5 -> 4 -> 3 -> 8 -> 7 -> 6 -> nullptr
(最后一部分小于K, 则不用再反转)

K = 4
=>
4 -> 3 -> 2 -> 1 -> 8 -> 7 -> 6 -> 5 -> nullptr
(head和tail都发生了变化)

1
2
3
4
5
6
7
8
9
10
11
12
13

• 接到题目先明确1, 2个具体的例子, e.g. 如上; 尽量在前面搞清需要留意的大部分乃至所有细节, 例如以上的K=4时, head是会发生改变的;
• 基本思路分析:
  • 此题很容易想到是基本的递归方法, 由于是逆序反转, 则应该是"递"的过程走到最后的节点(current == tail), 然后开始反转，首先状态参数应该是有前一个节点; 再者, 由于是K个一组，所以需要往递归实现的函数里塞入当前链表节点的索引计数idx, 在"归"的过程中, 想办法通过这个idx计算出当前节点是否达到第K个了； 如果是非递归手工栈实现， 则这些一般是要入栈的信息;
  • 计数是否K个一组的办法是, 在tail处用idx和K做模得到offset, 那么向前移动K步, 计数的条件是下一个节点的idx % k == offset + 1的位置, 即满足一组;
  • idx % K == offset + 1的节点, 不能再指向前一个节点, 而是指向下一组的第一个节点; 所以在"归"的过程中还需要做一些标记任务:
    • 在每一组开始的第一个节点(idx % k == offset)的时候, 需要标记当前节点是下一组k个元素的头节点需要指向的元素(next_pre_group_last);
    • 在每一组的最后一个节点(idx % K == offset + 1)时, 把当前节点指向前一组的第一个节点(pre_group_last), 更新pre_group_last的值为next_pre_group_last;
    • tail节点, 标记pre_group_last为tail-next (nullptr), next_pre_group_last为tail;
• 递归函数的状态参数:
  • head, tail, 是链表头尾;
  • curr, prev是链表的当前和上一个, 为了在"归"的过程中设定反转;
  • K, idx: 分别是K和当前链表节点的计数索引;
• 注意, head的指向可能是会发生改变的; 当K个一组, 恰好消耗完整个链表， head应该指向第一组的末尾节点; 所以递归状态的返回值应该非void而是struct Node* head;

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int val;
    struct Node* next;
};

struct Node* reverseLinkList(struct Node* head, struct Node* tail,
    struct Node* prev, struct Node* curr, int k, int idx) {
        static int offset  = 0;
        static bool back = false;
        static struct Node* pre_group_last = nullptr;
        static struct Node* next_pre_group_last = nullptr;

        if (curr != tail && back != true) {
            reverseLinkList(head, tail, curr, curr->next, k, ++idx);
        }

        if (curr == tail) {
            back = true;
            offset = idx % k;
            pre_group_last = tail->next;
            next_pre_group_last = tail;
            tail->next = prev;
            return curr;
        }

        int j = idx - 1;

        bool b_section_end = j % k == (offset + 1) % k;
        bool b_first_section = j < k - offset;
        if (!b_section_end && !b_first_section) {
            curr->next = prev;
        }

        if (b_section_end) {
            curr->next = pre_group_last;
            pre_group_last = next_pre_group_last;
            if (b_first_section) {
              head = next_pre_group_last;
            }
        }

        if (j % k == offset) {
            next_pre_group_last = curr;
        }

        return head;
}

std::pair<struct Node*, struct Node*> makeLinkedList() {
  struct Node* tail = new Node{8, nullptr};
  struct Node* n7 = new Node{7, tail};
  struct Node* n6 = new Node{6, n7};
  struct Node* n5 = new Node{5, n6};
  struct Node* n4 = new Node{4, n5};
  struct Node* n3 = new Node{3, n4};
  struct Node* n2 = new Node{2, n3};
  struct Node* head = new Node{1, n2};

  return std::make_pair(head, tail);
};

int main() {
    int k[] = {2, 3, 4, 5};

    std::for_each(begin(k), end(k), [&](int i) {
        pair<struct Node*, struct Node*> list = makeLinkedList();
        cout << "K =" << i << endl;
        cout << "before reverse: " << endl;
        for (struct Node* p = list.first; p != nullptr; p = p->next)
            cout << p->val << ", ";
        cout << endl;

        struct Node* head = reverseLinkList(list.first, list.second, nullptr, list.first, i, 0);
        cout << "after reverse: " << endl;
        for (struct Node* p = head; p != nullptr; p = p->next) {
            cout << p->val << ", ";
        }
        cout << endl;
    });
}

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85