K个一组反转链表_每k个一组翻转链表

K个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

题目解析

1.k个一组分别翻转，这就要我们要能对链表进行分组，每组是k个节点，各组单独翻转，意味着每组的翻转是组内行为，不可影响到别组，我在此处使用键值对pair将每组翻转前的头结点及尾结点存储起来
2.需要注意的是若节点总数不是k的倍数，多出的节点不翻转，那么需要设一个标志，标明存不存在不需要翻转的组别。
3.翻转链表一个简明高效的做法就是利用哑结点，结合头插法完成翻转
4.一些细节：k个一组划分后，需要将组与组之间的联系切开，防止组内翻转时影响别组；如果节点总数不是k的倍数，最后一组需要重新链接；

代码

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(k==1 || head->next == nullptr)
            return head;
        vector<pair<ListNode*, ListNode*>> q;
        while(head!=nullptr){//k组分割
            q.push_back({head,nullptr});//加入新组，并填入头结点
            int cnt = 1;
            while(head!=nullptr && cnt%k!=0){//k个一组
                head = head->next;
                ++cnt;
            } 
            q.back().second = head;//新组尾结点填充,
            if(head)
                head = head->next;
        }
        bool flag = q.back().second==nullptr?true:false;//判断最后一组是否需要翻转(true:不需要 false:需要)
        int n = q.size();
        n -= flag?1:0;//有不需要翻转的个数需要-1     
        for(int i = 0; i < n; ++i){
            q[i].second->next = nullptr;//尾部断开链接，实现每组独立	
            if(i == 0)
                head = Reverse(q[i].first);
            else
                q[i-1].first->next = Reverse(q[i].first);
        }
        if(flag)//不需要翻转的组别需要重新链接
            q[n-1].first->next = q.back().first;
        return head;
    }
private:
    ListNode* Reverse(ListNode* head){//翻转链表
        ListNode* dummy = new ListNode(0);//哑结点
        dummy->next = head;
        ListNode* rear = head->next;
        head->next = nullptr;//断开与旧链的链接
        while(rear != nullptr){
            ListNode* back = rear->next;
            rear->next = dummy->next;
            dummy->next = rear;
            rear = back;
        }
        return dummy->next;
    }
};
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

算法分析

在分割链表时，while循环遍历节点，算法时间复杂度为O(n)；
在翻转链接新链时，for循环算法复杂度为O(n/k),因为for循环内部调用Reverse函数，Reverse函数时间复杂度为O(k)，因此，在这一步骤，时间复杂度为O(n/k)*O(k)=O(n),因此整个算法时间复杂度为O(n)。

至于算法的空间复杂度，该算法申请了一个键值对数组存储节点组，因此算法空间复杂度为O(2*n/k),即O(n)