Brute Force Approach
In the brute force approach to merge two sorted linked lists, we can use a temporary node to store the starting node of the resulting linked list. We know that the tail pointer of a node in a linked list always points to the last node in the resulting list so we can append nodes easily. Hence, while merging we need to compare the values of both the linked lists and make the pointer of the resulting list point to the suitable node. In this way, when the iterations are completed over all the nodes then we will get a linked list obtained by merging two sorted linked lists.
Pseudocode
The pseudocode to merge two sorted linked lists is as follows:
- Create two temporary nodes, start and tail nodes for the linked list.
- If Linked list 1 is null, then the tail node of the resulting linked list will point to Linked list 2 and if Linked list 2 is null, then the tail node will point to Linked list 1.
- Compare the data from both nodes of Linked list 1 and Linked list 2 and make the tail node point to the node containing higher value.
- Continue the comparison and keep pointing the tail node to one of the nodes from the given linked lists till one of the linked lists is completely traversed.
- If one of the given linked lists is completed, then add the remaining elements to the tail node of the resulting linked list and display the output.
Implementation in Java
/* Program to merge two sorted linked lists */
import java.util.*;
/* Linked list node structure */
class LLNode
{
int info;
LLNode next;
LLNode(int t)
{
info = t;
next = null;
}
}
class MergeLinkedLists
{
LLNode head;
/* Method to insert a node at the end of the linked list */
public void addToLast(LLNode node)
{
if (head == null)
{
head = node;
}
else
{
LLNode temp = head;
while (temp.next != null)
temp = temp.next;
temp.next = node;
}
}
/* Method to display linked list */
void displayList()
{
LLNode temp = head;
while (temp != null)
{
System.out.print(temp.info + " ");
temp = temp.next;
}
System.out.println();
}
// Main program
public static void main(String args[])
{
MergeLinkedLists llist1 = new MergeLinkedLists();
MergeLinkedLists llist2 = new MergeLinkedLists();
llist1.addToLast(new LLNode(1));
llist1.addToLast(new LLNode(5));
llist1.addToLast(new LLNode(8));
llist1.addToLast(new LLNode(10));
llist2.addToLast(new LLNode(3));
llist2.addToLast(new LLNode(6));
llist2.addToLast(new LLNode(9));
llist2.addToLast(new LLNode(12));
llist1.head = new List().sortedMerge(llist1.head, llist2.head);
llist1.displayList();
}
}
class List
{
LLNode sortedMerge(LLNode headA, LLNode headB)
{
LLNode temporaryLLNode = new LLNode(0);
/* tail points to the last node in resulting linked list */
LLNode tail = temporaryLLNode;
while (true)
{
/* if either list runs out,
use the other list */
if (headA == null)
{
tail.next = headB;
break;
}
if (headB == null)
{
tail.next = headA;
break;
}
if (headA.info <= headB.info)
{
tail.next = headA;
headA = headA.next;
}
else
{
tail.next = headB;
headB = headB.next;
}
/* Advance the tail */
tail = tail.next;
}
return temporaryLLNode.next;
}
}

You can also try this code with Online Java Compiler
Run Code
Implementation in C++
// Program to merge two sorted linked lists
#
include < bits / stdc++.h >
using namespace std;
/* Linked list node */
class LLNode
{
public:
int info;
LLNode * next;
};
void MoveLLNode(LLNode ** destRef, LLNode ** sourceRef);
LLNode * MergeSortedList(LLNode * a, LLNode * b)
{
LLNode temporary;
LLNode * tail = & temporary;
temporary.next = NULL;
while (1)
{
if (a == NULL)
{
tail - > next = b;
break;
}
else if (b == NULL)
{
tail - > next = a;
break;
}
if (a - > info <= b - > info)
MoveLLNode( & (tail - > next), & a);
else
MoveLLNode( & (tail - > next), & b);
tail = tail - > next;
}
return (temporary.next);
}
void MoveLLNode(LLNode ** destRef, LLNode ** sourceRef)
{
LLNode * newLLNode = * sourceRef;
assert(newLLNode != NULL);
*sourceRef = newLLNode - > next;
newLLNode - > next = * destRef;
*destRef = newLLNode;
}
void push(LLNode ** head_ref, int new_info)
{
LLNode * new_node = new LLNode();
new_node - > info = new_info;
new_node - > next = ( * head_ref);
( * head_ref) = new_node;
}
void displayList(LLNode * node)
{
while (node != NULL)
{
cout << node - > info << " ";
node = node - > next;
}
}
int main() {
LLNode * res = NULL;
LLNode * a = NULL;
LLNode * b = NULL;
push( & a, 10);
push( & a, 8);
push( & a, 5);
push( & a, 1);
push( & b, 12);
push( & b, 9);
push( & b, 6);
push( & b, 3);
res = MergeSortedList(a, b);
displayList(res);
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Output:
1 3 5 6 8 9 10 12
Complexity Analysis
Time Complexity: In this approach, we are traversing through the complete linked lists of sizes m and n, therefore, the time complexity is O(m+n).
Space Complexity: The space complexity is O(1), because the space for storing m and n nodes in both linked lists is already occupied by the given linked lists and for implementing this program, we need constant space, i.e., O(1).
If the space occupied by m and n number of nodes is also considered, then the space complexity will be O(m+n).
Merge two sorted linked lists using Dummy Nodes:
This approach creates a dummy node to serve as the head of the merged LinkedList. Initially, the tail pointer points to this dummy node and moves to the last node of the result list.
Algorithm
- Declare two node pointers, named “dummy node” and “tail,” and initialize them to null. These will be used to create the resulting merged linked list.
- If List1 is null, then set ‘tail.next’ to point to List2, and If List2 is null, then set ‘tail.next’ to point to List1.
- Compare the data of the nodes at the heads of List1 and List2, and perform the following tasks:
- Suppose List1.data is less than List2.data, then set ‘tail.next’ to point to a new node containing ‘List1.data’ and update ‘List1’ to ‘List1.next’.
- Otherwise, set ‘tail.next’ to point to a new node containing ‘List2.data’, and update ‘List2’ to ‘List2.next’.
- If both lists are not fully iterated, move the tail pointer to ‘tail.next’, and repeat from Step 1.
- If both lists are fully iterated, return ‘dummyNode.next’ as the head of the merged linked list, containing all the elements sorted in ascending order.
Merge two sorted linked lists using Recursion:
This approach will use the recursion technique to merge two sorted linked lists.
Algorithm
- Create a function named ‘mergeLinkedList(list1, list2)’. It has passed two parameters named ‘list1’ and ‘list2’.
- Check if ‘list1’ is empty. If it is, return ‘list2’ as the result.
- Similarly, if ‘list2’ is empty, return ‘list1’ as the result.
- Compare the data of the current nodes in ‘list1’ and ‘list2’.
-
Suppose the data of the current node in list1 is less than the data of the current node in ‘list2’. If it is true, then perform the following:
- Call the ‘mergeLinkedList’ function again with the next node of ‘list1’ and the same 'list2'.
- Return ‘list1’ as the merged result.
-
Otherwise, if the data of the current node in ‘list 2’ is less than or equal to the data of the current node in ‘list1’. If it is true, then perform the following:
- Call the ‘mergeLinkedList’ function again with the same ‘list1’ and the next node of ‘list2’.
- Return ‘list 2’ as the merged result.
Merge two sorted linked lists by Reversing the Lists:
In this approach, we'll reverse both the linked lists so they are in decreasing order. Then, we'll compare the first elements of each list and add the smaller one to the end of the result list.
Algorithm
- Create two new Nodes named "res" and "temp" and initialize both with NULL.
- Execute a while loop as long as both "head1" and "head2" are not NULL, and perform the following steps:
-
Check if the data in "head1" is greater than or equal to the data in "head2".
- If true, assign "temp" with the "head1.next" node.
- Make 'head1.next' point to the current 'res' node.
- Update 'res' to point to "head1".
- Move 'head1' to the node stored in 'temp’.
-
If the condition in step 1 is false, the 'head2' data is greater. In this case:
- Set 'temp' to point to the 'head2.next' node.
- Update 'head2.next' to the current 'res' node.
- Update 'res' to point to 'head2'.
- Move 'head2' to the node stored in 'temp'.
- After completing the loop, return the 'res' node, representing the merged linked list.
Frequently Asked Questions
Why is merge sort preferred for linked lists?
Linked lists may not have nodes adjacent in memory and therefore, we can insert items efficiently in the middle with the help of the merge operation of merge sort without using extra space.
Which algorithm is best suited to merge two linked lists?
An iterative approach is considered the best way to merge two linked lists. This approach is simple and effective, with an O(n+m) complexity. In this, we compare the current value nodes, select the smaller one, and move the pointer forward till it reaches the end.
How many minimum comparisons are required for merge sort?
In the best-case scenario, merging two sorted arrays of size 'n' needs a minimum of 'n' comparisons with elements sorted in ascending order. The average case depends on the element order, while the worst case, with elements sorted in descending order, needs '2n' comparisons.
Conclusion
In this article we discussed the approach to merge two sorted linked lists and display the resulting linked list.
Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problems, interview experiences, for placement preparations.
Nevertheless, you may consider our paid courses to give your career an edge over others!
Do upvote our blogs if you find them helpful and engaging!
Happy Learning!