Leetcode
Published in
2 min readJun 18, 2021
--
21. Merge Two Sorted Lists
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:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]Example 2:
Input: l1 = [], l2 = []
Output: []Example 3:
Input: l1 = [], l2 = [0]
Output: [0]Constraints:
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100- Both
l1andl2are sorted in non-decreasing order.
Solution1: Iteratively
class Solution:
def mergeTwoLists1(self, l1, l2):
dummy = cur = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
cur.next = l1
l1 = l1.next else:
cur.next = l2 l2 = l2.next
cur = cur.next
cur.next = l1 or l2
return dummy.next# TC: O(m+n), where m, n are the lengths of the two linked lists
# SC: O(1)
Solution2: Recursively
class Solution:
def mergeTwoLists2(self, l1, l2):
if not l1 or not l2:
return l1 or l2
if l1.val < l2.val:
l1.next = self.mergeTwoLists2(l1.next, l2)
return l1 else:
l2.next = self.mergeTwoLists2(l1, l2.next)
return l2
# TC: O(m+n)
# SC: O(m+n)
Solution3:in-place Iteratively
class Solution:
def mergeTwoLists(self, l1, l2):
if None in (l1, l2):
return l1 or l2
dummy = cur = ListNode(0)
dummy.next = l1
while l1 and l2:
if l1.val < l2.val:
l1 = l1.next
else:
nxt = cur.next
cur.next = l2
tmp = l2.next
l2.next = nxt
l2 = tmp cur = cur.next
cur.next = l1 or l2
return dummy.next# TC: O(m+n)
# SC: O(1)
