LeetCode刷题之合并排序链表

2018-06-18 02:11:42来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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

给定实例:
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)。此外就没有了,时间复杂度就是递归所花费的时间。

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Python 全栈开发:python的推导式(列表推导式、字典推导式、集

下一篇:PyCharm设置仿sublime配色__Py版本2018.1