.jpeg)
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
1
2
| Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]
|
Example 2:
1
2
| Input: l1 = [], l2 = []
Output: []
|
Example 3:
1
2
| Input: l1 = [], l2 = [0]
Output: [0]
|
遞迴尋訪兩個串列，依序回傳。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| Time: O(n), Space: O(n)
# 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, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists(l1.next,l2)
return l1
else:
l2.next = self.mergeTwoLists(l1,l2.next)
return l2
|