[数据结构与算法]Leetcode004:合并两个有序链表

题解

第一种解法:递归

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list1 is None:
            return list2
        elif list2 is None:
            return list1
        elif list1.val<list2.val:
            list1.next = self.mergeTwoLists(list1.next,list2)
            return list1
        else:
            list2.next = self.mergeTwoLists(list1,list2.next)
            return list2

时间和内存：

时间复杂度：O(n+m)
空间复杂度：O(n+m）

第二种解法:迭代

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prehead = ListNode(-1)
        prev = prehead
        
        while list1 and list2:
            if list1.val<=list2.val:
                prev.next = list1
                list1 =list1.next
            else:
                prev.next = list2
                list2 =list2.next
            prev=prev.next
        
        prev.next = list1 if list1 is not None else list2
        
        return prehead.next

图解：

时间和内存：

时间复杂度：O(n+m)
空间复杂度：O(1）