合并两个有序链表

题目很简单，主要是注意递归的写法。

image.png

• 我的解法：迭代法

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        if list2 is None:
            return list1
        if list1 is None:
            return list2
# 迭代法
        mergelist = ListNode()
        cur = mergelist
        while list1 is not None and list2 is not None:
            if list1.val < list2.val:
                cur.next = list1
                cur = cur.next
                list1 = list1.next
            elif list1.val >= list2.val:
                cur.next = list2
                cur = cur.next
                list2 = list2.next
        if list1 is None:
            cur.next = list2
        elif list2 is None:
            cur.next = list1
        return mergelist.next

• 题解：递归法，O(m+n)

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