Leetcode 21 - Merge Two Sorted Lists
Explanation for Leetcode 21 - Merge Two Sorted Lists problem, and its solution in Python.
Problem
Leetcode 21. Merge Two Sorted Lists
Example:
1
2
3
4
5
6
7
8
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Input: list1 = [], list2 = []
Output: []
Input: list1 = [], list2 = [0]
Output: [0]
Approach
We can use a dummy node to start the merged list and a pointer to keep track of the tail of the merged list. Then we can iterate through both lists, compare the values, and append the smaller value to the merged list. We also need to move the pointer of the list that we appended from forward. Once we reach the end of one of the lists, we can append the remaining list to the merged list.
Visual representation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4
dummy = -1 -> None
curr = -1
since list1.val (1) <= list2.val (1), we append list1 to the merged list.
dummy = -1 -> 1 -> None
curr = 1
list1 = 2 -> 4
list2 = 1 -> 3 -> 4
since list1.val (2) > list2.val (1), we append list2 to the merged list.
dummy = -1 -> 1 -> 2 -> None
curr = 1
list1 = 2 -> 4
list2 = 3 -> 4
since list1.val (2) <= list2.val (3), we append list1 to the merged list.
dummy = -1 -> 1 -> 2 -> None
curr = 2
list1 = 4
list2 = 3 -> 4
since list1.val (4) > list2.val (3), we append list2 to the merged list.
dummy = -1 -> 1 -> 2 -> 3 -> None
curr = 3
list1 = 4
list2 = 4
since list1.val (4) <= list2.val (4), we append list1 to the merged list.
dummy = -1 -> 1 -> 2 -> 3 -> 4 -> None
curr = 4
list1 = None
list2 = 4
Since list1 is now None, we append list2 to the merged list then exit the loop and return dummy.next as it is the head of the merged list.
dummy = -1 -> 1 -> 2 -> 3 -> 4 -> 4 -> None
Here is the implementation of the approach:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
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
if list1:
curr.next = list1
elif list2:
curr.next = list2
return dummy.next
Time Complexity and Space Complexity
The time complexity is $ O(n + m) $ where $ n $ is the length of list1 and $ m $ is the length of list2 because we iterate through both lists once.
The space complexity is $ O(1) $ because we are not using any extra space.