leetcode 25. K 个一组翻转链表

​
​

作者简介：C/C++ 、Golang 领域耕耘者，创作者
个人主页：作者主页
活动地址：CSDN21天学习挑战赛
题目来源： leetcode官网
如果感觉博主的文章还不错的话，还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

💜 题目描述

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

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例1：

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

示例2：

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

提示：
链表中的节点数目为 n
1 <= k <= n <= 5000
0 <= Node.val <= 1000

🧡 算法分析

这题是 24. 两两交换链表中的节点 的进阶版

算法思路：

1. 先判断链表后面是否有k个节点
2. 将后面k个节点进行翻转

翻转步骤

• 因为是翻转k个节点，这里就跟上面的那题有区别了，此题需要先将内部节点进行翻转（一个循环）
• 修改外部前面的指针
• 修改外部连接下一个链表的指针

💚 代码实现

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        auto dummy = new ListNode(-1);
        dummy->next = head;
        for(auto p = dummy; ;)
        {
            auto q = p;
            // 向后遍历k个元素，看是否存在k个节点
            for(int i = 0; i < k && q; i ++) q = q->next;
            if(!q) break;  // 没有k个节点直接返回链表就行了
            auto a = p->next, b = a->next;
            // 修改k个节点中内部的指针
            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 是一轮翻转后的最后节点，也是也一轮需要翻转的前一个节点
            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
24
25
26
27

执行结果：

💙 时间复杂度分析

其中遍历一次， 时间复杂度为O(n)

如果觉得对你有帮助的话:
👍 点赞，你的认可是我创作的动力！
🧡 收藏，你的青睐是我努力的方向！
✏️ 评论，你的意见是我进步的财富！