当前位置:软件基础->数据结构 ->LeetCode刷题之合并排序链表

原创版权标志LeetCode刷题之合并排序链表

作者:阿郎  发表时间:2018/4/4 8:03:49  阅读:
[摘要] 合并两个有序链表并返回一个新的列表。新列表应该由连接在一起的节点前两个列表
使用支付宝扫码领红包,余额宝付款才可以使用红包哦!不要忘记哈。每天扫一次,天天赚红包!!可以将二维码保存到手机,每天直接扫码领红包啦!!

    要求: 合并两个有序链表并返回一个新的列表。新列表应该由连接在一起的节点前两个列表

    给定实例:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

思路分析:
引入第三个链表,存储合并之后的链表,开两个指针,分别遍历两个链表,当遍历到一个节点的时候,就开始判断大小,然后将小的链表节点存储到第三个链表中,依次递归判断。但是我们需要考虑临界条件,如果第一个链表的数都比第二个链表的小,那么我们就直接将第二个链表链接到第三个链表的next域中就行。
代码如下:
class ListNode:
 def __init__(self, x):
 self.val = x
 self.next = None

class Solution:
 def mergeTwoLists(self, l1, l2):
 if l1 is None:
 return l2
 if l2 is None:
 return l1
 pMerge = ListNode(None)
 if l1.val < l2.val:
 pMerge = l1
 pMerge.next = self.mergeTwoLists(l1.next, l2)
 else:
 pMerge = l2
 pMerge.next = self.mergeTwoLists(l1, l2.next)
 return pMerge

分析下开销: 额外的内存是引入的第三个链表,而空间大小就是O(n)。此外就没有了,时间复杂度就是递归所花费的时间。
微信扫码关注公众号CPP技术网,微信号cpp_coder,关注我们的公众号,阅读更多精彩内容!每天还可以领取大红包哦!!!每天还可以领取大红包哦!!!每天还可以领取大红包哦!!!
文章来源:C++技术网原创文章版权为网站和作者共同所有,会员文章禁止转载。非会员文章转载做好本文超链接即表示授权转载。通过文章下面的分享按钮可以自由分享所有文章。

返回顶部

在线提问
问题标题:
问题描述:(简陋的描述会导致问题被最后回答、没有针对性回答甚至无法解答。请确保问题描述的足够清楚。)