一、前言
本系列文章为《剑指Offer》刷题笔记。
刷题平台:牛客网
书籍下载:共享资源
二、题目
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
1、思路
先判断输入的链表是否为空的指针。如果第一个链表为空,则直接返回第二个链表;如果第二个链表为空,则直接返回第一个链表。如果两个链表都是空链表,合并的结果是得到一个空链表。
两个链表都是排序好的,我们只需要从头遍历链表,判断当前指针,哪个链表中的值小,即赋给合并链表指针即可。使用递归就可以轻松实现。
2、代码
C++:
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 28 29 30 31 | /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { //判断指针是否为空 if(pHead1 == NULL){ return pHead2; } else if(pHead2 == NULL){ return pHead1; } ListNode* pMergedHead = NULL; if(pHead1->val < pHead2->val){ pMergedHead = pHead1; pMergedHead->next = Merge(pHead1->next, pHead2); } else{ pMergedHead = pHead2; pMergedHead->next = Merge(pHead1, pHead2->next); } return pMergedHead; } }; |
Python2.7:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | # -*- coding:utf-8 -*- # class ListNode: # def __init__(self, x): # self.val = x # self.next = None class Solution: # 返回合并后列表 def Merge(self, pHead1, pHead2): # write code here if not pHead1: return pHead2 if not pHead2: return pHead1 pMergeHead = None if pHead1.val < pHead2.val: pMergeHead = pHead1 pMergeHead.next = self.Merge(pHead1.next, pHead2) else: pMergeHead = pHead2 pMergeHead.next = self.Merge(pHead1, pHead2.next) return pMergeHead |

微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
2019年5月14日 下午6:50 沙发
这个递归如何才能跳出来?
2019年5月14日 下午9:34 1层
@政治部 条件在最前面,没有子节点了就返回。
2019年5月15日 下午10:32 板凳
那这个函数最终返回的是递归终止条件里面的返回值吗?return pHead2或者 return pHead1?
2019年5月16日 下午6:35 1层
@政治部 递归到最里面,然后再从里往外释放,最终到的就是需要的链表。
2019年6月27日 下午12:24 地板
关于Python的算法,严格意义上不算递归吧。没有“有回”呀,这算是迭代吧。
2019年6月27日 下午9:42 1层
@小小毛 递归一定有return,要不然程序就死了。
2019年8月23日 上午10:00 4楼
楼主你好~问个有点傻的问题。。是每次调用这个递归函数他才有一个return是吗?所以就是返回pMergeHead然后加上如果两个链表长度不相等剩下的部分,是吗
2019年8月26日 上午9:49 1层
@yyx 不是啊,不满足条件,不会return的,return了就不往下递归了,开始往上返回。
2020年4月24日 上午8:44 5楼
请问您如果只用python编写代码,不会C++编写代码,今年8月份左右找工作, 从现在开始牛客网剑指offer,到8月份能找工作吗?本专业是电子信息工程
2020年4月24日 上午9:58 1层
@zymize 看岗位的,开发岗必须c++,算法岗看面试官心情,c++和python都行。刷题时间是够的,但还得补其他专业知识,时间紧,加油~
2020年4月24日 上午10:05 2层
@Jack Cui 非常感谢。请问如果是算法岗的话大概还需要掌握哪些专业知识呢?麻烦能给些建议吗?我是女生,逻辑上面没有那么强。或者有没有推荐女生去的岗?
2020年4月24日 上午11:06 3层
@zymize 那时间有点紧迫的,看我这篇:
https://cuijiahua.com/blog/2018/04/life_2.html
你应该能有个大概的了解,去各个公司招聘网站看一看吧,看下喜欢哪个,看看要求,合不合适自己看了更清楚。
不过不论哪个岗位,时间都是有些紧张的,得抓紧了。
2020年7月20日 下午7:30 1层
@zymize 同学你现在找到了吗?咱俩同专业,可能还是同一个学校???
2021年2月22日 上午8:59 6楼
python3.*的解法,可行不?
a = [1,2,3,4,5]
b = [2,3,4,5,6]
a.extend(b)
a.sort()
print(a)
2021年9月17日 下午11:04 7楼
返回的是链表的尾节点吧。
2021年9月18日 上午8:47 8楼
如果两个链表不一样长返回的是比另一条链表所有数都大的数所在的节点