题目很简单，主要是注意递归的写法。
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
