Merge Two Sorted Linked Lists

Problem Statement

Given two linked lists which are sorted in increasing order. Merge both lists into a single linked list which is also sorted in increasing order.

Example

Input :

Output:

Explanation

As we can see that if we merge both lists and arrange them in increasing order, it will become 1->2->3->4->4->6->7->8->9.

Constraints

$1 <= |List1| <= 10^6$ (1 <= Size of the first linked list <= $10^6$)
$1 <= |List2| <= 10^6$ (1 <= Size of the second linked list <= $10^6$)
$1 <= \text{Node.data} <= 10^6$ (1 <= Value of the Nodes <= $10^6$)

Approach 1 (Using Recursion)

In this approach, we will use Recursion to merge two sorted linked lists. This is one of the easiest approaches to solving this problem. The main intuition behind the approach is that we can keep the track of current nodes in both lists through the recursive function by passing the current nodes as a parameter. The node with the lesser node value will be updated in the recursive call each time. This will lead to the merging of two lists.

Algorithm

• Create a new Node named result
• Check if the head1 is empty, and return head2
• Check if head2 is empty, return head1
• Now find the node which has the smaller value (head1 or head2)
• Update the result with that node and call the recursive function accordingly
• Finally, return the result

C++ Implementation

Output

Java Implementation

Output

Python Implementation

Output

Complexity Analysis

Time Complexity Analysis In this algorithm, we are using recursion to merge two sorted linked lists, and the recursion will use the time complexity equal to the sum of lengths of both the list, i.e. O(N+M) or in general we can consider it as O(N) time complexity

So the total worst-case time complexity for this approach to merge two sorted linked lists is O(N) + O(M) = O(N+M) = O(N)

Space Complexity Analysis In this approach, we are using recursion and the recursion will take space complexity equal to the sum of lengths of both the list, i.e. O(N+M) or in general we can consider it as O(N) space complexity

Time Complexity: O(N) Space Complexity: O(N)

Approach 2 (Using Temporary Dummy Node)

In this approach, we will use a temporary dummy node as a start of the resultant list. The main intuition behind this approach is that first we will create a dummy node and we will add the new nodes at its rear end, which will be created by comparing the current nodes of both the lists i.e. the new node will be created with a smaller node value among both lists, finally, we will return the dummy.next, which will be the final result.

Algorithm

• Create two new Nodes named dummy and result
• Initialize result as &dummy (initializing result with the address of the dummy node).
• Initialize dummy.next with null
• If any of the head1 or head2 is null, then update the result's next pointer with the other node and break out of the loop.
• Now find the node which has the smaller value (head1 or head2)
• Update the result's next pointer with that node and move that node one step forward.
• Finally return the dummy's next pointer.

C++ Implementation

Output

Java Implementation

Output

Python Implementation

Output

Complexity Analysis

Time Complexity Analysis In this algorithm, we are running a loop while either of the head1 or head2 will become null which will take time complexity equal to the minimum of lengths of both the list, i.e. min(O(N+M)) or in general we can consider it as O(N) time complexity

So the total worst-case time complexity for this approach to merge two sorted linked lists is min(O(N), O(M)) = O(N)

Space Complexity Analysis In this approach we are just using two variables i.e. Nodes to store the pointers, so we are using constant extra space and we can consider it as O(1) space complexity

Time Complexity: O(N) Space Complexity: O(1)

Approach 3 (Using Local References)

In this approach, we will use a local reference to store the pointers by their address, so that the changes which we will make in the pointers are reflected in the original resultant node. The main intuition behind this approach is that we will create a pointer to the node which points to the last node and initialize it with the result, which is initialized with null. After every comparison, we will update this last pointer, and we will move to its next, and automatically our result will also be updated.

Algorithm

• Create two new Nodes named lastptr and result.
• Initialize the result as null and lastptr as &result (initializing lastptr with the address of the result node).
• If any of the head1 or head2 is null, then update lastptr pointer with the other node and break out of the loop.
• Now find the node which has the smaller value (head1 or head2).
• Update the lastref pointer with that node and move that node one step forward.
• Move the lastref pointer one step forward.
• Finally return the result node.

C++ Implementation

Output

Java Implementation

Output

Python Implementation

Output

Complexity Analysis

Time Complexity Analysis In this algorithm, we are running a loop while either of the head1 or head2 will become null which will take time complexity equal to the minimum of lengths of both the list, i.e. min(O(N+M)) or in general we can consider it as O(N) time complexity

So the total worst-case time complexity for this approach to merge two sorted linked lists is min(O(N), O(M)) = O(N)

Space Complexity Analysis In this approach we are just using two variables i.e. Nodes to store the pointers, so we are using constant extra space and we can consider it as O(1) space complexity

Time Complexity: O(N) Space Complexity: O(1)

Approach 4 (Reversing the Linked Lists)

In this approach, we will reverse both lists. The main intuition behind this approach is that we will first create two nodes temp and res, and then reverse both lists. We will keep track of our result in the res node and the temp node is used for swapping the res node and the node which is to be added. We will add the head of the current greatest node to the result. By doing this we are building our resultant list in the reverse order.

Algorithm

• Create two new Nodes named res and temp.
• Initialize both res and temp with NULL.
• Now run a while loop while head1 and head2 are not null and perform the following steps :
  • if head1's data>=head2's data, then initialize temp with head1's next, head1's next with res, res with head1, and change head1 to temp.
  • initialize temp with head2's next, head2's next with res, res with head2, and change head2 to temp.
• Finally return the res node.

C++ Implementation

Output

Java Implementation

Output

Python Implementation

Output

Complexity Analysis

Time Complexity Analysis

• In the first step, we are reversing both the linked lists which will perform the operations equal to the lengths of the linked lists i.e. O(N) + O(M)
• In the second step, we are running 3 loops, the first loop will perform the operations equal to the minimum of the length of both the lists, the second loop will perform the remaining operations left till the head1 becomes null and the third loop will also perform the remaining operations left till the head2 becomes null.
• So the total time complexity taken in step two will be O(N)+O(M).

So the total worst-case time complexity for this approach to merge two sorted linked lists is O(N)+O(M)+O(N)+O(M) = 2 * O(N) + 2 * O(M) or in general we can consider it as O(N) time complexity

Space Complexity Analysis In this approach we are just using two variables i.e. Nodes to store the pointers, so we are using constant extra space and we can consider it as O(1) space complexity

Time Complexity: O(N) Space Complexity: O(1)