力扣(LeetCode)25. K 个一组翻转链表(C++)

模拟

前置知识 : 反转链表、两两交换链表中的节点 。 LeetCode 有相应题目，可以先做。

---

设置哑结点 ， 便于操作头结点。 翻转至少要 $k$ 个结点 ， 先检查剩余结点够不够 $k$ 个。 不够 $k$ 个就翻转完成了。

翻转分为组内翻转和首尾变向两步 。 如图所示 ， 当 $k=3$ ， $1$ -> $2$ -> $3$ 变成 $3$ -> $2$ -> $1$ 就是组内翻转 。 $O$ -> $3$ ， $1$ -> $4$ 就是首尾变向 。

模拟组内翻转 。 对于第一组，组前结点 $p=O$ 。 用 $a$ 表示 $p$ -> $next$ ，$b$ 表示 $a$ -> $next$ ，$c$ 表示 $b$ -> $next$ 。 让 $b$ -> $next=a$ 完成反向 ， $a=b,b=c$ 让 $a、b$ 后移。组内 $k$ 个点之间的连接线一共 $k-1$ 条，循环 $k-1$ 次 ， 完成组内翻转 。

组内翻转的最后 ， $a$ 为组内第一个结点 ， $b$ 为下一组的第一个结点 ， 组前结点 $p$ 的指向没有变过 ， $p$ -> $next$ 依然指向翻转前的第一个点 ，所以首尾变向很容易完成 ， 见代码。

代码展示

C++

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        auto p= dummy;
        while(1){
            auto t = p;
            for(int i = 0;i<k&&t;i++) t = t->next;//检查k个结点够不够。
            if(!t) break;//剩余结点不足k个
            auto a = p->next , b = a->next;
            for(int i = 0;i<k-1;i++){
                auto c = b->next;
                b->next = a;
                a = b , b = c;
            }
            auto c = p->next;
            p->next = a, c ->next = b;
            p = c;
        }
        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

1. 时间复杂度 : $O(n)$ ， $n$ 是链表长度，翻转链表的时间复杂度 $O(n)$ ，遍历链表的时间复杂度$O(n)$ ， 二者是相加关系 ， 每个结点最多被遍历两遍 ， 总时间复杂度 $O(2n)$ ， 忽略常数时间复杂度 $O(n)$ 。
2. 空间复杂度: $O(1)$ ， 除若干变量占用的常量级空间，没有使用额外的线性空间

AC