In merge two sorted linked lists we have given head pointer of two linked lists, merge them such that a single linked list is obtained which has nodes with values in sorted order. return the head pointer of the merged linked list.
Note: merge the linked list in-place without using any extra space.
Table of Contents
Example
Input
Output
Types of solution
- Recursive
- Iterative
Recursive
Approach for Merge Two Sorted Linked Lists
The idea is to recursively merge the two input linked list such that the sorted order in the merged linked list is maintained.
Algorithm
- Define the base case: if any of the linked lists is empty, simply return the other.
- Now compare data values of head nodes of both the linked lists (x and y):
- if x.data < y.data => x.next = recurse{x.next,y}.
- Else => y.next = recurse{x,y.next}.
- return the head of the recursively merged linked list.
Implementation
C++ program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* blue print of node */
class Node
{
public:
int data;
Node *next;
Node(int num)
{
data = num;
next = NULL;
}
};
/* append a node at the end of the Linked List */
Node* insert(Node *head,int data)
{
if(head == NULL)
head = new Node(data);
else
{
Node* temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = new Node(data);
}
return head;
}
/* print the Linked List */
void print(Node *head)
{
if(head != NULL)
{
cout<<head->data<<" ";
print(head->next);
}
}
/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
Node *sortedMerge(Node* x,Node* y)
{
if(x == NULL)
return y;
if(y == NULL)
return x;
if(x->data < y->data)
{
x->next = sortedMerge(x->next,y);
return x;
}
else
{
y->next = sortedMerge(x,y->next);
return y;
}
}
/* function to implement above */
int main()
{
Node *x = NULL, *y = NULL;
/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
cout<<"First Linked List : ";
print(x);
cout<<endl;
/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
cout<<"Second Linked List : ";
print(y);
cout<<endl;
/* merge the 2 Linked Lists and print */
cout<<"Merged Linked List in Sorted Order : ";
Node *result = sortedMerge(x,y);
print(result);
return 0;
}First Linked List : 3 4 7 9 Second Linked List : 1 2 5 6 8 Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9
Java Program
import java.util.*;
import java.io.*;
class TutorialCup
{
/* blue print of node */
static class Node
{
int data;
Node next;
Node(int num)
{
data = num;
next = null;
}
};
/* append a node at the end of the Linked List */
static Node insert(Node head,int data)
{
if(head == null)
head = new Node(data);
else
{
Node temp = head;
while(temp.next != null)
temp = temp.next;
temp.next = new Node(data);
}
return head;
}
/* print the Linked List */
static void print(Node head)
{
if(head != null)
{
System.out.print(head.data + " ");
print(head.next);
}
}
/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
static Node sortedMerge(Node x,Node y)
{
if(x == null)
return y;
if(y == null)
return x;
if(x.data < y.data)
{
x.next = sortedMerge(x.next,y);
return x;
}
else
{
y.next = sortedMerge(x,y.next);
return y;
}
}
/* function to implement above */
public static void main (String[] args)
{
Node x = null, y = null;
/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
System.out.print("First Linked List : ");
print(x);
System.out.println();
/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
System.out.print("Second Linked List : ");
print(y);
System.out.println();
/* merge the 2 Linked Lists and print */
System.out.print("Merged Linked List in Sorted Order : ");
Node result = sortedMerge(x,y);
print(result);
}
}First Linked List : 3 4 7 9 Second Linked List : 1 2 5 6 8 Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9
Complexity Analysis
- Time Complexity: T(n) = O(a+b).
- Space Complexity: A(n) = O(1)
a = size of the first linked list.
b = size of the second linked list.
Iterative
Approach for Merge Two Sorted Linked Lists
The idea is to convert recursive code into an iterative one.
Algorithm
- creates two node pointers head and tail.
- assign head.next = new Node(-1), allocating dummy node to head so that it becomes easy to merge both the linked list. the head pointer is used to retain the head of the merged linked list.
- the tail is used to store the end of the merged linked list, the tail pointer is used append nodes from x and y at the end of the merged list.
- Traverse both the input lists x and y simultaneously until reaching the end of one of them.
- For each node of x and y consider:
- if x.data < y.data => tail.next = x and move to next node in list x.
- Else tail.next = y and move to the next node in list y.
- If during traversal any of the list x or y becomes empty, simply append the nonempty list to the merged list.
- In the end return head.next.
Implementation
C++ program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
/* blue print of node */
class Node
{
public:
int data;
Node *next;
Node(int num)
{
data = num;
next = NULL;
}
};
/* append a node at the end of the Linked List */
Node* insert(Node *head,int data)
{
if(head == NULL)
head = new Node(data);
else
{
Node* temp = head;
while(temp->next != NULL)
temp = temp->next;
temp->next = new Node(data);
}
return head;
}
/* print the Linked List */
void print(Node *head)
{
if(head != NULL)
{
cout<<head->data<<" ";
print(head->next);
}
}
/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
Node* utility(Node* x,Node* y)
{
/* head is used to return head of the merged linked list */
Node *head = new Node(-1);
/* tail is used to append a node at end
of the merged linked list at each step */
Node *tail = head;
/* process until one of the linked list becomes empty */
while(x && y)
{
if(x->data < y->data)
{
tail->next = x;
x = x->next;
}
else
{
tail->next = y;
y = y->next;
}
tail = tail->next;
}
/* if any of the linked list gets exhausted
append the other one to the merged list */
if(x == NULL)
tail->next = y;
if(y == NULL)
tail->next = x;
return head->next;
}
/* function to merge two sorted linked
lists using a utility function */
Node *sortedMerge(Node* x,Node* y)
{
if (x == NULL)
return y;
if (y == NULL)
return x;
/* start with the linked list whose head data is the lesser */
if (x->data < y->data)
return utility(x,y);
else
return utility(y,x);
}
/* function to implement above */
int main()
{
Node *x = NULL, *y = NULL;
/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
cout<<"First Linked List : ";
print(x);
cout<<endl;
/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
cout<<"Second Linked List : ";
print(y);
cout<<endl;
/* merge the 2 Linked Lists and print */
cout<<"Merged Linked List in Sorted Order : ";
Node *result = sortedMerge(x,y);
print(result);
return 0;
}First Linked List : 3 4 7 9 Second Linked List : 1 2 5 6 8 Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9
Java Program
import java.util.*;
import java.io.*;
class TutorialCup
{
/* blue print of node */
static class Node
{
int data;
Node next;
Node(int num)
{
data = num;
next = null;
}
};
/* append a node at the end of the Linked List */
static Node insert(Node head,int data)
{
if(head == null)
head = new Node(data);
else
{
Node temp = head;
while(temp.next != null)
temp = temp.next;
temp.next = new Node(data);
}
return head;
}
/* print the Linked List */
static void print(Node head)
{
if(head != null)
{
System.out.print(head.data + " ");
print(head.next);
}
}
/* function that merges 2 Linked Lists keeping the Sorted
Order & returns the head of of the merged Linked List */
static Node utility(Node x,Node y)
{
/* head is used to return head of the merged linked list */
Node head = new Node(-1);
/* tail is used to append a node at end
of the merged linked list at each step */
Node tail = head;
/* process until one of the linked list becomes empty */
while(x != null && y != null)
{
if(x.data < y.data)
{
tail.next = x;
x = x.next;
}
else
{
tail.next = y;
y = y.next;
}
tail = tail.next;
}
/* if any of the linked list gets exhausted
append the other one to the merged list */
if(x == null)
tail.next = y;
if(y == null)
tail.next = x;
return head.next;
}
/* function to merge two sorted linked
lists using a utility function */
static Node sortedMerge(Node x,Node y)
{
if (x == null)
return y;
if (y == null)
return x;
/* start with the linked list whose head data is the lesser */
if (x.data < y.data)
return utility(x,y);
else
return utility(y,x);
}
/* function to implement above */
public static void main (String[] args)
{
Node x = null, y = null;
/* construct the first Linked List */
x = insert(x,3);
x = insert(x,4);
x = insert(x,7);
x = insert(x,9);
System.out.print("First Linked List : ");
print(x);
System.out.println();
/* construct the second Linked List */
y = insert(y,1);
y = insert(y,2);
y = insert(y,5);
y = insert(y,6);
y = insert(y,8);
System.out.print("Second Linked List : ");
print(y);
System.out.println();
/* merge the 2 Linked Lists and print */
System.out.print("Merged Linked List in Sorted Order : ");
Node result = sortedMerge(x,y);
print(result);
}
}First Linked List : 3 4 7 9 Second Linked List : 1 2 5 6 8 Merged Linked List in Sorted Order : 1 2 3 4 5 6 7 8 9
Complexity Analysis
- Time Complexity: T(n) = O(a+b).
- Space Complexity: A(n) = O(1), head and tail pointers are used which take constant memory.
a = size of the first linked list.
b = size of the second linked list.