剑指OFFER之合并两个排序的链表
2024-10-08 11:51:06
题目描述
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
解决办法
1、递归方法:
if(pHead1==NULL)
return pHead2;
else if(pHead2==NULL)
return pHead1;
ListNode* pMerge=NULL;
if(pHead1->val<=pHead2->val){
pMerge=pHead1;
pMerge->next=Merge(pHead1->next,pHead2);
}
else{
pMerge=pHead2;
pMerge->next=Merge(pHead1,pHead2->next);
}
return pMerge;
2、非递归方法:
if(pHead1==NULL)
return pHead2;
if(pHead2==NULL)
return pHead1;
ListNode* pRet=NULL;
ListNode* pMerge=NULL;
if(pHead1->val<=pHead2->val){
pMerge=pHead1;
pHead1=pHead1->next;
}
else{
pMerge=pHead2;
pHead2=pHead2->next;
}
pRet=pMerge;
while(pHead1&&pHead2){
if(pHead1->val<=pHead2->val){
pRet->next=pHead1;
pHead1=pHead1->next;
pRet=pRet->next;
}
else{
pRet->next=pHead2;
pHead2=pHead2->next;
pRet=pRet->next;
}
}
if(pHead1==NULL)
pRet->next=pHead2;
if(pHead2==NULL)
pRet->next=pHead1;
return pMerge;
本解法困扰了我很久,因为开始时我只设置了一个pMerge指针,而没有设置pRet指针,结果运行后发现,如果是两个等长的序列,那么函数返回的结果只有两个序列的最后一个元素,我折腾了好久才明白,pRet是合并链表的工作指针,函数运行完成后它保存的就是链表的尾元素,而合并链表的真正的头指针是pMerge指针,它才是函数真正的返回结果。
最新文章
- 关于robotframework,app,appium的xpath定位问题及常用方法
- c# json序列化 意外字符i 意外字符&#239; 解决方案
- 如何获取URL中的参数
- SSH: 本地.ssh目录下的公钥文件最好删掉
- UItableView自定义标题(headerView)重用问题
- [笔记]--Ubuntu安装Sublime Text 2
- Node.js-require的使用方法
- JS扩展 或 Jquery的扩展写法
- Bootstrap入门(二十五)JS插件2:过渡效果
- zabbix 中文乱码的处理
- 20155219 2016-2017-2 《Java程序设计》第2周学习总结
- 0.1 Maven相关知识(项目开发基础)
- [JSOI2016]扭动的回文串
- 关于Unity中UI中的Slider,Toggle和InputField等节点
- apt get update无法正常使用解决方案(转载)
- python 清华镜像pip install
- 解决XAMPP不能启动Apche服务问题
- 并发编程学习笔记之Java存储模型(十三)
- Pandoc中的Markdown语法
- Python 进阶 之 socket模块