Given two sorted linked lists consisting of N and M nodes respectively. The task is to merge both of the list (in-place) and return the head of the merged list.
Input: Two lists of N and M nodes are provided
However, number of nodes are not the game changing factor, one can execute the operation even despite measuring the length.
Approach
Both the lists are sorted, it's a good idea to check either of the 1st node in the list which of them is smaller, consider that advance the pointer corresponding to the smaller node.
An example demonstrated in the following image:
In the end, when there is a left out nodes, we simply just append the nodes to the result list.
For the above approach,
Time Complexity: O(min(n, m))
i.e., The Smallest linked list travel amount.
Space Complexity: O(1)
i.e., No such extra auxiliary space required proportional to input.
Few implementations for the same can be found below.
1. Java implementation.
/*
Merge two linked lists
head pointer input could be NULL as well for empty list
Node is defined as
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
*/
class LinkedList
{
Node sortedMerge(Node head1, Node head2) {
Node res = new Node(-1);
Node itr = res;
while(head1 != null && head2 != null) {
if(head1.data <= head2.data) {
itr.next = head1;
head1 = head1.next;
} else {
itr.next = head2;
head2 = head2.next;
}
itr = itr.next;
}
fillRest(head1, itr);
fillRest(head2, itr);
return res.next;
}
void fillRest(Node head, Node itr) {
if(head != null)
itr.next = head;
}
}
2. JavaScript / Node.js implementation.
class Solution {
fillRest(head, itr) {
if(head !== null)
itr.next = head;
}
sortedMerge(head1, head2)
{
let res = new Node(-1);
let itr = res;
let getMin = () => {
let min;
if(head1.data <= head2.data) {
min = head1;
head1 = head1.next;
} else {
min = head2;
head2 = head2.next;
}
return min;
};
while(head1 !== null && head2 !== null) {
itr.next = getMin();
itr = itr.next;
}
this.fillRest(head1, itr);
this.fillRest(head2, itr);
return res.next;
}
}
3. C++ implementation.
/* Link list Node
struct Node {
int data;
struct Node *next;
Node(int x) {
data = x;
next = NULL;
}
};
*/
//Function to merge two sorted linked list.
Node* sortedMerge(Node* head1, Node* head2)
{
// code here
Node res(-1);
Node *itr = &res;
auto fillRest = [] (Node* head, Node* itr) {
if(head != NULL)
itr->next = head;
};
while(head1 != NULL && head2 != NULL) {
if(head1 -> data <= head2 -> data) {
itr-> next = head1;
head1 = head1 -> next;
} else {
itr-> next = head2;
head2 = head2 -> next;
}
itr = itr -> next;
}
fillRest(head1, itr);
fillRest(head2, itr);
return res.next;
}
Top comments (0)