当前位置:网站首页>链表中的节点每k个一组翻转
链表中的节点每k个一组翻转
2022-08-10 21:49:00 【干饭小白】
描述
将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表
如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。
数据范围: \ 0 \le n \le 2000 0≤n≤2000 , 1 \le k \le 20001≤k≤2000 ,链表中每个元素都满足 0 \le val \le 10000≤val≤1000
要求空间复杂度 O(1)O(1),时间复杂度 O(n)O(n)
例如:
给定的链表是 1\to2\to3\to4\to51→2→3→4→5
对于 k = 2k=2 , 你应该返回 2\to 1\to 4\to 3\to 52→1→4→3→5
对于 k = 3k=3 , 你应该返回 3\to2 \to1 \to 4\to 53→2→1→4→5
本题已AC
解题思路:
拿到这题,一个想法就是用栈来写。至于为什么我会想到用栈呢?因为需要反向嘛,这里我看题目的要求,空间复杂度为 O(1)。第一个想法是保存值,通过 new一个新的节点了实现。但是仔细一想,好像不可以的,因为这样空间复杂度肯定不符合,突然灵机一动,我们可以用栈保存节点是指针,nice.
1→2→3→4→5 k = 2时
1→2→3→4→5 k = 3时
4和5是不用翻转的,所以如果用栈又会带来一个问题,因为栈结构是先进后出的,如果用栈来保存肯定会导致,4,5也会被翻转。
这里有两个解决方法,
1.把4,5再次入栈(入另一个栈),然后再输出 ok
2.不妨我们不使用栈结构,我们使用双向队列(而且双向队列在前后两端进行插入删除的效率也挺高的,所以我们使用这个结构最佳了)
我们哪一个例子来看:
1→2→3→4→5 k = 3时
准备工作,一个指向该链表的指针 head。一个deque,一个中间变量 tmpk
一些方便操作的辅助指针 s和ans
这里我们做一个循环,while(head != nullptr) 是的,一次遍历就可以搞定
此时退出循环,okk
判断 que是否为空或者tmpk是否等于 0
如果que不为空的话,说明que此时的节点是不需要翻转的
所以
那么这题就ok了,当然题目有一些细节,这个只能根据实际的测试清空来修改了
比如 {},2 {1,2},3 {1},2等
附上我通过的代码:
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* reverseKGroup(ListNode* head, int k) {
// write code here
deque<ListNode*> sta;
int tmpk = k;
ListNode *s = nullptr;
ListNode *ans = nullptr;
while(head != nullptr)
{
sta.push_back(head);
head = head->next;
tmpk--;
if(tmpk == 0)
{
if(s == nullptr)
{
s = sta.back();
sta.pop_back();
ans = s;
}
while(!sta.empty())
{
s->next = sta.back();
sta.pop_back();
s = s->next;
}
tmpk = k;
}
}
while(!sta.empty())
{
if(s == nullptr)
{
s = sta.front();
sta.pop_front();
ans = s;
}
else
{
s->next = sta.front();
sta.pop_front();
s= s->next;
}
}
if(s != nullptr)
s->next = nullptr;
return ans;
}
};
边栏推荐
- QT笔记——QT工具uic,rcc,moc,qmake的使用和介绍
- shell编程之正则表达式与文本处理器
- Exploration and practice of the "zero trust" protection and data security governance system of the ransomware virus of Meichuang Technology
- uni-app微信小程序——下拉多选框
- 服务——DNS正向反向域名解析服务
- 财务年报怎样翻译,为什么要选择专业翻译公司?
- 测试4年感觉和1、2年时没什么不同?这和应届生有什么区别?
- FPGA - 7系列 FPGA内部结构之Memory Resources -03- 内置纠错功能
- 阿里云贾朝辉:云XR平台支持彼真科技呈现国风科幻虚拟演唱会
- Web Reverse Lilac Garden
猜你喜欢
Alibaba and Ant Group launched OceanBase 4.0, a distributed database, with single-machine deployment performance exceeding MySQL
Regular expression of shell programming and text processor
【开源教程5】疯壳·开源编队无人机-飞控固件烧写
企业云存储日常运行维护实践经验分享
VLAN huawei 三种模式
An article to teach you a quick start and basic explanation of Pytest, be sure to read
shell编程之免交互
Black cats take you learn Makefile article 13: a Makefile collection compile problem
使用SylixOS虚拟串口,实现系统串口自由
String类的常用方法
随机推荐
论文解读(g-U-Nets)《Graph U-Nets》
Huawei router clock near the drainage experiment (using stream strategy)
【SQL刷题】Day3----SQL必会的常用函数专项练习
FPGA - 7系列 FPGA内部结构之Memory Resources -03- 内置纠错功能
国内Gravatar头像的完美替代方案Cravatar
Why general company will say "go back messages such as" after the end of the interview, rather than just tell the interviewer the result?
Extended Chinese Remainder Theorem
基于Pix4Dmapper的空间三维模型重建应用——空间分析选址
元宇宙社交应用,靠什么吸引用户「为爱发电」?
MySQL高级指令
力扣221题,最大正方形
企业云存储日常运行维护实践经验分享
基于Pix4Dmapper的运动结构恢复法无人机影像三维模型重建
Labelme-5.0.1 version edit polygon crash
QT笔记——用VS + qt 生成dll 和 调用生成的dll
SDP
LeetCode Daily Question (1573. Number of Ways to Split a String)
3D model reconstruction of UAV images based on motion structure restoration method based on Pix4Dmapper
Black cat takes you to learn Makefile Part 11: When the header file a.h changes, how to recompile all the .c files that depend on the header file a.h
Exploration and practice of the "zero trust" protection and data security governance system of the ransomware virus of Meichuang Technology