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

2017年12月3日15:22:41 8 4,358 °C
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

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

2、代码

C++:

Python2.7:

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

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

目前评论:8   其中:访客  4   博主  4

    • 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了就不往下递归了,开始往上返回。