剑指Offer(十六):合并两个排序的链表

2017年12月3日15:22:41 13 5,864 °C
摘要

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

剑指Offer(十六):合并两个排序的链表

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台:牛客网

书籍下载:共享资源

二、题目

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

1、思路

先判断输入的链表是否为空的指针。如果第一个链表为空,则直接返回第二个链表;如果第二个链表为空,则直接返回第一个链表。如果两个链表都是空链表,合并的结果是得到一个空链表。

两个链表都是排序好的,我们只需要从头遍历链表,判断当前指针,哪个链表中的值小,即赋给合并链表指针即可。使用递归就可以轻松实现。

2、代码

C++:

Python2.7:

weinxin
微信公众号
分享技术,乐享生活:微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论:13   其中:访客  7   博主  6

    • avatar 政治部 来自天朝的朋友 谷歌浏览器  LYA-AL00 Build/HUAWEILYA-AL00 P1 9 上海市卢湾区 电信 1

      这个递归如何才能跳出来?

        • avatar Jack Cui Admin 来自天朝的朋友 Safari浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

          @政治部 条件在最前面,没有子节点了就返回。

        • avatar 政治部 来自天朝的朋友 谷歌浏览器  LYA-AL00 Build/HUAWEILYA-AL00 P1 9 中国 移动 1

          那这个函数最终返回的是递归终止条件里面的返回值吗?return pHead2或者 return pHead1?

            • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

              @政治部 递归到最里面,然后再从里往外释放,最终到的就是需要的链表。

            • avatar 小小毛 来自天朝的朋友 谷歌浏览器 Windows 7 天津市 天津大学 3

              关于Python的算法,严格意义上不算递归吧。没有“有回”呀,这算是迭代吧。

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                  @小小毛 递归一定有return,要不然程序就死了。

                • avatar yyx 来自天朝的朋友 火狐浏览器 Ubuntu Linux 北京市 电信 2

                  楼主你好~问个有点傻的问题。。是每次调用这个递归函数他才有一个return是吗?所以就是返回pMergeHead然后加上如果两个链表长度不相等剩下的部分,是吗 :shock:

                    • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                      @yyx 不是啊,不满足条件,不会return的,return了就不往下递归了,开始往上返回。

                    • avatar zymize 来自天朝的朋友 搜狗浏览器 Windows 10 黑龙江省哈尔滨市 电信 1

                      请问您如果只用python编写代码,不会C++编写代码,今年8月份左右找工作, 从现在开始牛客网剑指offer,到8月份能找工作吗?本专业是电子信息工程

                        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器  Android 10 Redmi K20 Pro Build/QKQ1.190825.002 北京市通州区 联通

                          @zymize 看岗位的,开发岗必须c++,算法岗看面试官心情,c++和python都行。刷题时间是够的,但还得补其他专业知识,时间紧,加油~

                            • avatar zymize 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 电信 1

                              @Jack Cui 非常感谢。请问如果是算法岗的话大概还需要掌握哪些专业知识呢?麻烦能给些建议吗?我是女生,逻辑上面没有那么强。或者有没有推荐女生去的岗?

                                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                                  @zymize 那时间有点紧迫的,看我这篇:
                                  https://cuijiahua.com/blog/2018/04/life_2.html
                                  你应该能有个大概的了解,去各个公司招聘网站看一看吧,看下喜欢哪个,看看要求,合不合适自己看了更清楚。
                                  不过不论哪个岗位,时间都是有些紧张的,得抓紧了。

                              • avatar 一书一世界 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市双城区 联通 2

                                @zymize 同学你现在找到了吗?咱俩同专业,可能还是同一个学校???