LeetCode刷题之合并排序链表
合并两个有序链表并返回一个新的列表。新列表应该由连接在一起的节点前两个列表
给定实例: 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)。此外就没有了，时间复杂度就是递归所花费的时间。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2018-04-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
