pta两个有序链表的合并_21.合并两个有序链表

90 阅读 0 评论 60 点赞

我是靠谱客的博主兴奋高跟鞋，最近开发中收集的这篇文章主要介绍pta两个有序链表的合并_21.合并两个有序链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

21.合并两个有序链表

思路一暴力借用外部空间

分别遍历两个链表，把数放到列表中，运用sort方法。再用尾插法，遍历列表，创建新的有序链表。

class Solution:
    def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:

        sum = []

        def list2num(node):
            while node != None:
                sum.append(node.val)
                node = node.next

        list2num(l1)
        list2num(l2)
        sum.sort()

        dummy_node = ListNode(-1)
        start_node = dummy_node 

        for i in sum:
            new = ListNode(i)
            dummy_node.next = new
            dummy_node = new
        return start_node.next

思路二递归

时间复杂度 O（m+n）每次递归调用都会去掉l1 或 l2 的头结点，至多会递归调用每个节点一次。

因此，时间复杂度取决于合并后的链表长度。

2. 空间复杂度 O（m+n）至多调用函数 mergeTwoLists （m+n）次，每次调用需要消耗栈空间。

因此，空间复杂度为O（m+n）

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

思路三迭代

先设立哨兵节点，为了好返回生成的链表

用两个指针分别遍历两个链表，直到一方为空。

遍历的过程中，比较两指针指向节点的大小，然后尾插法插入哨兵节点的next。

直到一方为空，再把剩余不为空的链表插入。

class Solution:
    def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:

        dummy_node = ListNode(-1)
        start_node = dummy_node

        while l1 and l2:
            if l1.val < l2.val:
                dummy_node.next = l1
                l1 = l1.next
            else:
                dummy_node.next = l2
                l2 = l2.next
            dummy_node = dummy_node.next
        return start_node.next