Linked lists are fundamental data structures in programming, providing an efficient way to organize and manipulate data. When dealing with two sorted linked lists, a common operation is joining them into a single one. In this article, we’ll learn how to merge two sorted linked lists using the recursive approach.
What is the Merge Two Sorted Lists Problem?
Just to recap, A linked list is a linear data structure in which elements are stored in nodes. Each node points to the next node in the sequence. When we say the list is sorted, it means that the elements are arranged in ascending or descending order.
Merging two sorted linked lists preserves this order, which makes it easier for search algorithms to perform efficiently. We usually find the data in two different lists and it becomes necessary to join them to work on it. Sometimes, we need to present the output in a combined way.
Here is the problem statement: We are given 2 sorted linked lists, sorted in ascending order and we have to merge them in a way that maintains the sorted order.
Let’s look at an example,
LinkedList 1 = 1→ 3→ 6
LinkedList 2 = 2→ 4→ 5
Resultant List = 1→ 2→ 3→ 4→ 5→ 6
We can see the resultant list is sorted and contains the elements of both lists.
Brute Force Approach
The simplest way to solve it is by using the brute-force approach. We can create a dummy node with a value of 0 to simplify this node and merge our present lists to this in sorted order. We will iterate both lists and keep adding the elements to this node.
Here are the steps involved in this straightforward technique:
- First of all, we will create a dummy node with a value of 0
- Now we will create a pointer current initially pointing to the dummy node.
- Iterate until both input lists (l1 and l2) are exhausted. Compare the values of the current nodes in l1 and l2.
- Create a new node with the smaller value and append it to the merged list.
- After the loop, if either l1 or l2 is not exhausted, append the remaining nodes to the merged list.
- Return dummy->next after all iterations.
The Time Complexity of this approach is O(max(m, n)), where m and n are the sizes of both the lists. The Space Complexity of this approach is O(max(m, n)).
Recursive Approach to Merge Two-Sorted Lists
In the recursive approach, we will use a recursion to merge two sorted linked lists. We first select the smaller of the current nodes from both lists and then recursively merge the remaining lists.
We will follow the same steps as we were following in the brute force approach. But we will use recursion to do it easily. Following are the steps involved in merging two sorted linked lists using a recursive approach:
- Firstly we will declare the base case for our recursive function that If either l1 or l2 is empty, return the other list
- Now, Compare the values of the current nodes in l1 and l2 and choose the smaller value as the current node for the merged list.
- If l1 has the smaller value, recursively call the recursive function with parameters l1->next and l2.
- If l2 has the smaller value, recursively call the recursive function with parameters l1 and l2->next.
- Return the current node (either l1 or l2) as the merged list.
C++ Code
Here is the C++ program to merge two sorted lists using recursion:
#include <bits/stdc++.h>
using namespace std;
// Definition for singly-linked list.
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
// Base cases: if either list is empty, return the other list
if (!l1) return l2;
if (!l2) return l1;
// Choose the smaller value as the current node
if (l1->val < l2->val) {
// Recursively merge the rest of the lists starting from l1->next and l2
l1->next = mergeTwoLists(l1->next, l2);
return l1;
} else {
// Recursively merge the rest of the lists starting from l1 and l2->next
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}
int main() {
// Example usage
// Create sorted linked lists
ListNode* list1 = new ListNode(1);
list1->next = new ListNode(3);
list1->next->next = new ListNode(6);
ListNode* list2 = new ListNode(2);
list2->next = new ListNode(4);
list2->next->next = new ListNode(5);
// Merge the lists
ListNode* mergedList = mergeTwoLists(list1, list2);
// Print the merged list
while (mergedList) {
cout << mergedList->val << " ";
mergedList = mergedList->next;
}
return 0;
}Python Code
Here is the Python program to merge two sorted linked lists:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
# Create a dummy node to serve as the head of the merged list
dummy = ListNode()
current = dummy
# Loop until one of the lists is empty
while l1 and l2:
if l1.val < l2.val:
# Attach the current node to the smaller node from l1
current.next = l1
l1 = l1.next
else:
# Attach the current node to the smaller node from l2
current.next = l2
l2 = l2.next
# Move the current pointer to the last node
current = current.next
# Attach the remaining nodes from the non-empty list (if any)
if l1:
current.next = l1
elif l2:
current.next = l2
# Return the merged list starting from the dummy node's next
return dummy.next
# Example usage
list1 = ListNode(1, ListNode(3, ListNode(6)))
list2 = ListNode(2, ListNode(4, ListNode(5)))
mergedList = mergeTwoLists(list1, list2)
# Print the merged list
while mergedList:
print(mergedList.val, end=" ")
mergedList = mergedList.nextJava Code
You can implement it in Java as well:
public class MergeSortedLinkedLists {
static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// Create a dummy node to simplify the code
ListNode dummy = new ListNode(0);
ListNode current = dummy;
// Iterate while both lists are not empty
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
// If one list is not empty, append the remaining nodes
if (l1 != null) {
current.next = l1;
} else {
current.next = l2;
}
// Return the merged list starting from the next of the dummy node
return dummy.next;
}
// Helper method to print the merged list
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
// Example usage
ListNode list1 = new ListNode(1);
list1.next = new ListNode(3);
list1.next.next = new ListNode(6);
ListNode list2 = new ListNode(2);
list2.next = new ListNode(4);
list2.next.next = new ListNode(5);
// Merge the lists
ListNode mergedList = mergeTwoLists(list1, list2);
// Print the merged list
System.out.println("Merged List:");
printList(mergedList);
}
}Output:
1 2 3 4 5 6 The time complexity of merging two sorted lists using recursion is O(n), where n is the total number of nodes in both linked lists. This is because the function processes each node exactly once, and the number of recursive calls is proportional to the total number of nodes in the input lists.
The Space Complexity is O(n) (due to the function call stack during recursion), O(1) auxiliary space.
In the end, here you can compare both approaches and see that recursive is the best one:
| Approach | Time complexity | Space complexity | Details |
| Brute force | O(max(m, n)) | O(max(m, n)) | Create a dummy node with a value of 0 to simplify this node and merge our present lists to this in sorted order. |
| Recursive | O(n) | O(1) | Using recursion to save time and space. |
Another interesting problem related to linked lists is to detect a cycle.
Conclusion
While this problem looks easy at first glance, it is very difficult to find the solution instantly in a solution. That’s why it is also included in leetcode and other interview question websites as well. But now you know how to merge two sorted linked lists using the recursion, along with its time and space complexities.
