21. Merge Two Sorted Lists
Problem Description
You are given two sorted linked lists list1
and list2
. Your task is to merge these two linked lists into a single sorted linked list. This new list should retain all the nodes from both list1
and list2
, and it must be sorted in ascending order. The final linked list should be constructed by connecting the nodes from the two lists directly, which is similar to splicing. The function should return the new list's head node.
Intuition
The intuition behind the given solution approach comes from the fact that both list1
and list2
are already sorted. The algorithm can take advantage of this by comparing the nodes from both lists and choosing the smaller one to be the next node in the merged list. This selection process is repeated until one of the lists is exhausted.
We start by creating a dummy node, which is a typical technique used in linked list operations where the head of the result list is unknown. The dummy
node acts as a non-invasive placeholder to build our solution without knowing the head in advance; after the merge operation, the actual head of the merged list will be dummy.next
.
A pointer named curr
is assigned to keep track of the end of the already built part of the merged list; it starts at the dummy
node. We use a while
loop to iterate as long as there are elements in both list1
and list2
. During each iteration, we compare the values of the current heads of both lists and append the smaller node to the next
of curr
, moving list1
or list2
and curr
forward.
When the loop ends because one of the lists is empty, we know that all the remaining elements in the non-empty list must be larger than all elements already merged because the lists were sorted initially. So, we can simply point the next
of curr
to the non-empty list to complete the merge. Finally, we return the actual start of the merged list, which is dummy.next
.
Learn more about Recursion and Linked List patterns.
Solution Approach
The solution is implemented using a simple iterative approach which traverses both input linked lists simultaneously, always taking the next smallest element to add it to the merged linked list. The main data structure used here is the singly-linked list. The algorithm employs the classic two-pointer technique to merge the lists.
Here are the step-by-step details of the algorithm:
- A dummy node is created; this node does not hold any meaningful value but serves as the starting point of the merged linked list.
- A
curr
pointer is initialized to point at the dummy node. This pointer moves along the new list as nodes are added. - A
while
loop continues as long as there are elements in bothlist1
andlist2
. Inside the loop, a comparison is made:- If the value of the current node in
list1
is less than or equal to the value of the current node inlist2
, thenext
pointer ofcurr
is linked to the current node oflist1
, andlist1
is advanced to its next node. - Otherwise,
curr
next
is linked to the current node oflist2
, andlist2
is advanced to its next node.
- If the value of the current node in
- After each iteration,
curr
is moved to itsnext
node, effectively growing the merged list. - If one of the lists is exhausted before the other, the loop ends. Since one of the lists (either
list1
orlist2
) will beNone
, theor
operator in Python ensures thatcurr.next
will be linked to the remaining non-empty list. - Finally, the head of the merged list, which is immediately after the dummy node, is returned (
dummy.next
), thus omitting the dummy node which was just a placeholder.
This algorithm provides a clean and efficient way to traverse through two sorted lists, merging them without requiring additional space for the new list, as it reuses the existing nodes from both lists. It effectively adheres to the O(n) time complexity, where n is the total number of nodes in both lists combined, because each node is visited exactly once.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider the following small example to illustrate the solution approach. Suppose we have two linked lists:
List1: 1 -> 3 -> 5 List2: 2 -> 4 -> 6
We want to merge List1
and List2
into a single sorted linked list.
-
First, we create a dummy node. It doesn't store any data but will serve as an anchor point for our new list.
-
We initialize a
curr
pointer to the dummy node. Thiscurr
will be used to keep track of the last node in our merged list. -
Now we enter our
while
loop. Since bothList1
andList2
have elements, we make comparisons:- We compare
List1's
head (1) withList2's
head (2). Since 1 is less than 2, we linkcurr
toList1's
head and advanceList1
to the next element (which makes it 3 now).
- We compare
-
The list starts to form: Dummy -> 1.
Curr
now moves to 1. -
In the next comparison,
List1's
value (3) is greater thanList2's
value (2). So we linkcurr
toList2's
head and advanceList2
to the next element (which makes it 4 now). -
The list now is: Dummy -> 1 -> 2.
Curr
moves forward to 2. -
As we continue this process, the next comparison has
List1's
value (3) less thanList2's
value (4), so we linkcurr
toList1's
head and moveList1
forward. -
The list now looks like: Dummy -> 1 -> 2 -> 3.
Curr
moves to 3. -
This process of comparing and moving forward continues until we reach the end of one list. In this example, the merged list sequence goes: Dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6, after exhaustively comparing:
- 3 is less than 4
- 5 is greater than 4
- 5 is less than 6
-
Since we've reached the end of
List1
(there are no more elements to compare), we linkcurr
to the remainingList2
(which is just 6 now). -
We've reached the end of both lists, and our merged list is: Dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6.
-
Finally, we return
dummy.next
as the head of the new list, which omits the dummy node. So our final merged list is 1 -> 2 -> 3 -> 4 -> 5 -> 6.
Throughout the traversal, we only moved forward, directly connecting the smaller node from either list to the merged list, until we completely traversed both lists and combined them into one sorted list.
Solution Implementation
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def mergeTwoLists(self, list1: ListNode, list2: ListNode) -> ListNode:
8 # Creating a sentinel node which helps to easily return the head of the merged list
9 sentinel = ListNode()
10
11 # Current node is used to keep track of the end of the merged list
12 current = sentinel
13
14 # Iterate while both lists have nodes
15 while list1 and list2:
16 # Choose the smaller value from either list1 or list2
17 if list1.val <= list2.val:
18 current.next = list1 # Append list1 node to merged list
19 list1 = list1.next # Move to the next node in list1
20 else:
21 current.next = list2 # Append list2 node to merged list
22 list2 = list2.next # Move to the next node in list2
23
24 # Move the current pointer forward in the merged list
25 current = current.next
26
27 # Add any remaining nodes from list1 or list2 to the merged list
28 # If one list is fully traversed, append the rest of the other list
29 current.next = list1 if list1 else list2
30
31 # The sentinel node's next pointer points to the head of the merged list
32 return sentinel.next
33
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int val;
6 ListNode next;
7
8 ListNode() {}
9
10 ListNode(int val) { this.val = val; }
11
12 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
13}
14
15public class Solution {
16
17 /**
18 * Merge two sorted linked lists and return it as a new sorted list.
19 * The new list should be made by splicing together the nodes of the first two lists.
20 *
21 * @param list1 First sorted linked list.
22 * @param list2 Second sorted linked list.
23 * @return The head of the merged sorted linked list.
24 */
25 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
26 // Initialize a dummy node to act as the head of the merged list.
27 ListNode dummyHead = new ListNode();
28 // This pointer will be used to add new elements to the merged list.
29 ListNode current = dummyHead;
30
31 // As long as both lists have elements, keep iterating.
32 while (list1 != null && list2 != null) {
33 if (list1.val <= list2.val) { // If list1's value is less or equal, add it next.
34 current.next = list1;
35 list1 = list1.next; // Move to the next element in list1.
36 } else { // If list2's value is less, add it next.
37 current.next = list2;
38 list2 = list2.next; // Move to the next element in list2.
39 }
40 current = current.next; // Move forward in the merged list.
41 }
42
43 // In case one of the lists has remaining elements, link them to the end.
44 current.next = (list1 == null) ? list2 : list1;
45
46 // dummyHead.next points to the head of the merged list.
47 return dummyHead.next;
48 }
49}
50
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode() : val(0), next(nullptr) {}
7 * ListNode(int x) : val(x), next(nullptr) {}
8 * ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13 // Merges two sorted linked lists into one sorted linked list
14 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
15 // Creates a dummy head node to facilitate easy return and manipulation of the merged list.
16 ListNode* dummyHead = new ListNode();
17 // Maintains the current node pointer in the merged list.
18 ListNode* current = dummyHead;
19
20 // Traverse both lists while both have elements.
21 while (list1 && list2) {
22 // Compare the current values from both lists to determine which node to take next.
23 if (list1->val <= list2->val) {
24 // Take the node from list1 and advance the list1 pointer.
25 current->next = list1;
26 list1 = list1->next;
27 } else {
28 // Take the node from list2 and advance the list2 pointer.
29 current->next = list2;
30 list2 = list2->next;
31 }
32 // Advance the pointer in the merged list.
33 current = current->next;
34 }
35
36 // Append the non-empty remainder of the list to the merged list.
37 // If list1 is not empty, append it; otherwise, append list2.
38 current->next = list1 ? list1 : list2;
39
40 // The dummy head's next points to the start of the merged list,
41 // so return dummyHead->next.
42 return dummyHead->next;
43 }
44};
45
1// Definition for singly-linked list node
2interface ListNode {
3 val: number; // The value of the node
4 next: ListNode | null; // The reference to the next node
5}
6
7/**
8 * Merge two sorted linked lists and return it as a new sorted list.
9 * The new list should be made by splicing together the nodes of the first two lists.
10 *
11 * @param list1 - The head node of the first linked list.
12 * @param list2 - The head node of the second linked list.
13 * @returns The head node of the merged linked list.
14 */
15function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
16 // If one of the lists is null, return the other list since there's nothing to merge
17 if (list1 === null || list2 === null) {
18 return list1 || list2;
19 }
20
21 // Compare the values of the two list heads and recursively merge the rest of the lists
22 if (list1.val < list2.val) {
23 // If the value of the first list head is less,
24 // link that node to the result of merging the rest of the lists
25 list1.next = mergeTwoLists(list1.next, list2);
26 return list1;
27 } else {
28 // If the value of the second list head is less or equal,
29 // link that node to the result of merging the rest of the lists
30 list2.next = mergeTwoLists(list1, list2.next);
31 return list2;
32 }
33}
34
Time and Space Complexity
Time Complexity
The time complexity of the code is O(n + m)
, where n
and m
are the lengths of list1
and list2
respectively. This is because the while loop continues until we reach the end of one of the input lists and during each iteration of the loop, it processes one element from either list1
or list2
. Therefore, in the worst case, the loop runs for the combined length of list1
and list2
.
Space Complexity
The space complexity of the code is O(1)
. While we are creating a dummy
node and a curr
pointer, the space they use does not scale with the input size, as they are just pointers used to form the new linked list. No additional data structures are used that depend on the input size, so the space used by the algorithm does not grow with the size of the input lists.
Learn more about how to find time and space complexity quickly using problem constraints.
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!