作者简介: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. 两两交换链表中的节点 的进阶版
算法思路:
翻转步骤
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;
}
};
执行结果:
其中遍历一次, 时间复杂度为O(n)
如果觉得对你有帮助的话:
👍 点赞,你的认可是我创作的动力!
🧡 收藏,你的青睐是我努力的方向!
✏️ 评论,你的意见是我进步的财富!