Linked lists are quite like arrays in their linear properties. We can merge two sorted arrays to form an overall sorted array. In this problem, we have to merge two sorted linked lists in place to return a new list which contains elements of both lists in a sorted fashion.
Table of Contents
Example
L1 = 1 -> 2 -> 9 L2 = 1 -> 3 -> 4
1 1 2 3 4 9
Approach
The simplest way to do it would be to use the two-pointer technique. Create a new empty list. Append the smaller elements among both the pointers and increment the corresponding pointer. This is a good approach but requires the creation of an extra list that consumes space.
The Optimal Approach should consume constant space only in order to do an in-place sorting. We can follow the iterative approach. We already have the nodes stored in both the lists. Create a new list pointer and its subsequent “next pointers” should point to predefined nodes in the memory. In this process, we create no new nodes.
Algorithm(Naive Approach)
- Create a function mergeTwoSortedLists() that takes two list pointers as arguments
- If either of the lists is NULL, return the other one
- Create a temp variable that will point to the smaller node among heads of both lists
- Now, at least, one node is appended to our result, so one head should be incremented
- This creates a subproblem. So, call the same recursive function and append it to temp
- If List1.value < List2.value
- temp = new ListNode(List1.value) , temp->next = mergeTwoSortedLists(List1->next , List2)
- If List2.value <= List1.value
- temp = new ListNode(List2.value) , temp->next = mergeTwoSortedLists(List1 , List2->next)
- Return temp to get the desired list
Algorithm(Optimal)
- Create a new list pointer which will be called dummy_head.
- Maintain its “prehead” (copy pointer) so that we can access the list head address.
- The “next pointers” of dummy_head should be manipulated in such a way that it points to the predefined nodes in lists l1 and l2.
- We can do the above task in following ways:
- Keep iterating the lists with pointers starting from their heads.
- Unless one of the lists is completely traversed:
- Append the smaller valued node from the two list pointers to the dummy_head, incrementing the corresponding pointer.
- Now, at least one of the pointers is NULL. So, append the non-null list to the dummy head.
- Return the head of the dummy list.
Implementation
C++ Program to Merge Two Sorted Lists
Naive Approach
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
if(!l1)
return l2;
if(!l2)
return l1;
listNode* temp;
if(l1->value < l2->value)
{
temp = new listNode(l1->value);
temp->next = mergeTwoSortedLists(l1->next , l2);
}
else
{
temp = new listNode(l2->value);
temp->next = mergeTwoSortedLists(l1 , l2->next);
}
return temp;
}
void print(listNode* head)
{
while(head)
{
cout << head->value << " ";
head = head->next;
}
cout << '\n';
return;
}
int main()
{
listNode* l1 = new listNode(1);
l1->next = new listNode(2);
l1->next->next = new listNode(9);
listNode* l2 = new listNode(1);
l2->next = new listNode(3);
l2->next->next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
return 0;
}
Optimal Method
#include <bits/stdc++.h>
using namespace std;
struct listNode
{
int value;
listNode* next;
listNode(int x)
{
value = x;
next = NULL;
}
};
listNode* mergeTwoSortedLists(listNode* l1 , listNode* l2)
{
listNode *dummy_head = new listNode(-1) , *prehead = dummy_head;
while(l1 && l2)
{
if(l1->value < l2->value)
{
dummy_head->next = l1;
l1 = l1->next;
}
else
{
dummy_head->next = l2;
l2 = l2->next;
}
dummy_head = dummy_head->next;
}
dummy_head->next = (l1 ? l1 : l2);
return prehead->next;
}
void print(listNode* head)
{
while(head)
{
cout << head->value << " ";
head = head->next;
}
cout << '\n';
return;
}
int main()
{
listNode* l1 = new listNode(1);
l1->next = new listNode(2);
l1->next->next = new listNode(9);
listNode* l2 = new listNode(1);
l2->next = new listNode(3);
l2->next->next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
return 0;
}
1 1 2 3 4 9
Java Program to Merge Two Sorted Lists
Naive Approach
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class merge_two_sorted_lists
{
public static void print(listNode head)
{
while(head != null)
{
System.out.print(head.value + " ");
head = head.next;
}
return;
}
public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
{
if(l1 == null)
return l2;
if(l2 == null)
return l1;
listNode temp;
if(l1.value < l2.value)
{
temp = new listNode(l1.value);
temp.next = mergeTwoSortedLists(l1.next , l2);
}
else
{
temp = new listNode(l2.value);
temp.next = mergeTwoSortedLists(l1 , l2.next);
}
return temp;
}
public static void main(String args[])
{
listNode l1 = new listNode(1);
l1.next = new listNode(2);
l1.next.next = new listNode(9);
listNode l2 = new listNode(1);
l2.next = new listNode(3);
l2.next.next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
}
}
Optimal Method
class listNode
{
int value;
listNode next;
listNode(int x)
{
value = x;
next = null;
}
}
class merge_two_sorted_lists
{
public static void print(listNode head)
{
while(head != null)
{
System.out.print(head.value + " ");
head = head.next;
}
return;
}
public static listNode mergeTwoSortedLists(listNode l1 , listNode l2)
{
listNode dummy_head = new listNode(-1) , prehead = dummy_head;
while(l1 != null && l2 != null)
{
if(l1.value < l2.value)
{
dummy_head.next = l1;
l1 = l1.next;
}
else
{
dummy_head.next = l2;
l2 = l2.next;
}
dummy_head = dummy_head.next;
}
dummy_head.next = ((l1 != null) ? l1 : l2);
return prehead.next;
}
public static void main(String args[])
{
listNode l1 = new listNode(1);
l1.next = new listNode(2);
l1.next.next = new listNode(9);
listNode l2 = new listNode(1);
l2.next = new listNode(3);
l2.next.next = new listNode(4);
print(mergeTwoSortedLists(l1 , l2));
}
}
1 1 2 3 4 9
Complexity Analysis
Time Complexity to Merge Two Sorted Lists
O(N + M), where N and M are the lengths of the two lists. We traverse both the lists once in both approaches, so both the algorithms are linear.
Space Complexity to Merge Two Sorted Lists
In the Optimal approach, it is important to understand that we only manipulate the pointers. So, the constant space for variables accounts for memory usage. Therefore, the optimal method has a space complexity of O(1). O(N + M) space is used in the naive approach discussed.