题目
-
You are given the heads of two sorted linked lists
list1andlist2.Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Example 1:
![[leetcode] 21. Merge Two Sorted Lists](https://ctyun-collect-0531.gdoss.xstore.ctyun.cn/files/2023/07/20/0c230d541528461c94f46f02c7284869.png "[leetcode] 21. Merge Two Sorted Lists")
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
list1andlist2are sorted in non-decreasing order.
思路
递归
代码
python版本：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if not list1 and not list2:
return None
root=ListNode()
if not list1:
root.val=list2.val
root.next=self.mergeTwoLists(list1,list2.next)
elif not list2:
root.val=list1.val
root.next=self.mergeTwoLists(list1.next,list2)
elif list1.val<list2.val:
root.val=list1.val
root.next=self.mergeTwoLists(list1.next,list2)
else:
root.val=list2.val
root.next=self.mergeTwoLists(list1,list2.next)
return root
