EasyBlind75Linked List
Merge Two Sorted Lists
You are given the heads of two sorted linked lists. Merge the two lists into one sorted list.
Examples
Input
list1 = [1,2,4], list2 = [1,3,4]
Output
[1,1,2,3,4,4]
Merged sorted list.
Input
list1 = [], list2 = []
Output
[]
Both lists are empty.
Constraints
- •
The number of nodes in both lists is in the range [0, 50] - •
-100 <= Node.val <= 100 - •
Both list1 and list2 are sorted in non-decreasing order.
Approaches
Combine both lists into an array, sort it, and create a new linked list.
CodeT: O((m+n) log(m+n)) | S: O(m+n)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(list1, list2):
values = []
curr = list1
while curr:
values.append(curr.val)
curr = curr.next
curr = list2
while curr:
values.append(curr.val)
curr = curr.next
values.sort()
dummy = ListNode(0)
curr = dummy
for val in values:
curr.next = ListNode(val)
curr = curr.next
return dummy.nextCompare nodes from both lists and attach the smaller one.
CodeT: O(m + n) | S: O(1)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(list1, list2):
dummy = ListNode(0)
curr = dummy
while list1 and list2:
if list1.val <= list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
curr.next = list1 if list1 else list2
return dummy.nextRecursively merge by choosing the smaller head.
Diagram
list1: 1->2->4, list2: 1->3->4
1<=1: merge(2->4, 1->3->4)
2>1: merge(2->4, 3->4)
2<=3: merge(4, 3->4)
4>3: merge(4, 4)
4<=4: merge(None, 4)->4
Result: 1->1->2->3->4->4
CodeT: O(m + n) | S: O(m + n)
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def merge_two_lists(list1, list2):
if not list1:
return list2
if not list2:
return list1
if list1.val <= list2.val:
list1.next = merge_two_lists(list1.next, list2)
return list1
else:
list2.next = merge_two_lists(list1, list2.next)
return list2Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Merge to Array | O((m+n) log(m+n)) | O(m+n) | Combine both lists into an array, sort it, and create a new linked list. |
| Iterative Merge | O(m + n) | O(1) | Compare nodes from both lists and attach the smaller one. |
| Recursive Merge | O(m + n) | O(m + n) | Recursively merge by choosing the smaller head. |
Merge to Array
T: O((m+n) log(m+n))S: O(m+n)
Combine both lists into an array, sort it, and create a new linked list.
Iterative Merge
T: O(m + n)S: O(1)
Compare nodes from both lists and attach the smaller one.
Recursive Merge
T: O(m + n)S: O(m + n)
Recursively merge by choosing the smaller head.
Common Mistakes
Not handling the case where one list is longer than the other
Forgetting to attach the remaining nodes of the non-empty list
Creating a cycle by not advancing the pointer after attaching a node