BM3链表中的节点每k个一组翻转

1.题目

BM3 链表中的节点每k个一组翻转

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

image-20230824140620807

2.解析

2.1 链表逆置

其他部分其实很好解决，基于链表逆置的代码（即逆置整个链表的代码）

我们只需要将每一个需要逆置的小区间的开头给记下来，交付给链表逆置就可以了。

1
2
3
4
5
6
7
8
9
10
11
// 无差别逆置
ListNode* reverseNode(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    ListNode* ans = reverseNode(head->next);
    head->next->next = head;
    head->next = nullptr;
    return ans;
}

2.2 记录每个需要逆置的区间

比如如下部分代码，为了方便进行遍历和指针控制，我创建了一个头节点放置在了原本链表开头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 头节点和遍历指针
ListNode phead(0);
phead.next = head;
ListNode* cur = &phead;
// 把每k个节点单独取出来，分别逆置后链接起来
std::vector<ListNode*> begin_node_v,begin_node_prev_v;
int index = k-1; // 初始化为k-1(忽略头节点)，原有链表第一个节点始终入栈
int node_count = 0;// 节点总数（包含头节点）
while (cur != nullptr) { // 不知道有多长，得死循环
    if(index+1 == k && cur != &phead){
        begin_node_prev_v.push_back(cur);
    }
    else if (index == k) {
        begin_node_v.push_back(cur);
        index = 0;
    }
    cur = cur->next;
    index++;
    node_count ++;
}

这里还创建了两个vector数组

  • begin_node_v：待逆置区间的开头
  • begin_node_prev_v：待逆置区间的开头的上一个

下面是对这两个数组的说明，如果给出的示例是如下形式

1
{1,2,3,4,5},2

那么两个数组分别存储了如下值

1
2
begin_node_v:     {1,3,5}
begin_node_prev_v: {2,4}

这样一来，第一个数组实际上存放的是每个区间的开头，第二个数组存放的则是每个区间的结尾。逆置了之后:

  • 第二个数组就是新区间的开头
  • 第一个数组就是新区间的结尾

方便我们将逆置后的链表重新连起来！

2.3 抛弃无需逆置的区间

在上面的循环中，用了node_count来计算了整个链表的长度，减1剔除我自己添加的头节点，就是原始链表的长度。

题目有个特殊要求：如果原始链表的长度并非k的整数倍，那么最后一段区域的链表是不需要逆置的

1
2
3
4
1 - 2 - 3 - 4 - 5
当k=3的时候，只需要逆置 1-2-3
            4-5不需要逆置
3 - 2 - 1 - 4 - 5

在这种情况，用例和两个数组存放的节点如下

1
2
3
4
用例 {1,2,3,4,5},3

begin_node_v:     {1,4}
begin_node_prev_v: {3}

如果我们直接将begin_node_v里面的节点交付给链表逆置函数，就会将4-5这一段夜给逆置，最终返回的结果是3-2-1-5-4，不符合题目要求！

所以在这种情况下，我们需要将4从第一个数组中删除！如果原视链表的节点数量已经小于k了，则也不需要逆置，直接返回即可。

1
2
3
4
5
6
7
8
9
10
11
// 如果节点总数量小于k则不逆置直接返回
node_count --;//减-1 头节点
if(node_count <k){
    return head;
}
// 不是整数倍，代表最后一个是不要处理的
ListNode* last_link = nullptr;
if((node_count %k) != 0) {
    last_link = begin_node_v[begin_node_v.size()-1];// 最后一个
    begin_node_v.pop_back();// 删除最后一个
}

另外，为了最终将这段么有逆置的链表和新链表连起来，我们还需用一个指针记录下这一段的开头；last_link初始化为空是方便后续的判断，如果为空代表不存在这一段链表，不需要链接。

2.4 区间结束标识

为了标识每次逆置的结束符，我们还需要将待逆置的每一个小区间的末尾都改成nullptr

1
2
3
4
// 将每个区间的末尾节点的next链接为Null作为递归标识
for(auto&n:begin_node_prev_v){
    n->next = nullptr;
}

2.5 逆置和重新链接

上面的步骤都敲定了之后，我们就可以将第一个数组begin_node_v的节点喂给链表逆置函数了，该逆置函数的返回值是新链表的开头。

1
2
3
4
5
6
7
// 将每个区间交付给递归开始逆置，并将逆置的返回值与上一个区间的开头连起来
cur = &phead;
for(auto& n:begin_node_v){
    ListNode* ptr=reverseNode(n);
    cur->next = ptr;
    cur = n;
}

这里说一下cur指针的作用，以用例{1,2,3,4,5},2为栗子，此时begin_node_v数组中存放的是{1,3,5}

  • 初始化为phead
  • 第一次循环，n指向的是1，cur指向的是phead；逆置结束后，ptr指向的是2，刚好就是新链表的开头，将cur的next链接为它，并将cur更新为1
  • 第二次循环，n指向的是3，cur指向的是1；逆置结束后，ptr指向的是4，此时cur的next指向它，就是将1的next链接为4，再次更新cur为3。
  • 第三次循环，n指向的是5，cur指向的是3；逆置结束后，将3的next链接为5，cur更新为5
  • 循环结束

结束时，这个链表就已经完工了！我们只需要判断一下还没有剩下的没有逆置的节点，将其链接给begin_node_v数组中的最后一个节点（也是逆置部分的最后一个节点）的next就可以了

1
2
3
4
// 判断是否还有剩下的节点
if(last_link !=nullptr){
    begin_node_v[begin_node_v.size()-1]->next = last_link;
}

3.完整代码

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
86
87
88
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类
     */
    // 无差别逆置
    ListNode* reverseNode(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* ans = reverseNode(head->next);
        head->next->next = head;
        head->next = nullptr;
        return ans;
    }

    void cout_vector(std::vector<ListNode*>& begin_node_v) {
        for (auto& e : begin_node_v) {
            cout << e->val << " " ;
        }
        cout << endl;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        // 只有一个节点，或者逆置区间为1的都不需要操作
        if (head == nullptr || head->next == nullptr || k <= 1) {
            return head;
        }
        // 头节点和遍历指针
        ListNode phead(0);
        phead.next = head;
        ListNode* cur = &phead;
        // 把每k个节点单独取出来，分别逆置后链接起来
        std::vector<ListNode*> begin_node_v,begin_node_prev_v;
        int index = k-1; // 初始化为k-1(忽略头节点)，原有链表第一个节点始终入栈
        int node_count = 0;// 节点总数（包含头节点）
        while (cur != nullptr) { // 不知道有多长，得死循环
            if(index+1 == k && cur != &phead){
                begin_node_prev_v.push_back(cur);
            }
            else if (index == k) {
                begin_node_v.push_back(cur);
                index = 0;
            }
            cur = cur->next;
            index++;
            node_count ++;
        }
        // 走到这里已经把每个需要逆置的开头节点给记录下来了
        // 如果节点总数量小于k则不逆置直接返回
        node_count --;//减-1 头节点
        if(node_count <k){
            return head;
        }
        // 不是整数倍，代表最后一个是不要处理的
        ListNode* last_link = nullptr;
        if((node_count %k) != 0) {
            last_link = begin_node_v[begin_node_v.size()-1];// 最后一个
            begin_node_v.pop_back();// 删除最后一个
        }

        // cout_vector(begin_node_v);
        // cout_vector(begin_node_prev_v);

        // 将每个区间的末尾节点的next链接为Null作为递归标识
        for(auto&n:begin_node_prev_v){
            n->next = nullptr;
        }
        // 将每个区间交付给递归开始逆置，并将逆置的返回值与上一个区间的开头连起来
        cur = &phead;
        for(auto& n:begin_node_v){
            ListNode* ptr=reverseNode(n);
            cur->next = ptr;
            cur = n;
        }
        // 判断是否还有剩下的节点
        if(last_link !=nullptr){
            begin_node_v[begin_node_v.size()-1]->next = last_link;
        }
        return phead.next;
    }
};

通过截图

image-20230824142627806