Merge Two Sorted Linked Lists
In this article let's learn how to merge two sorted linked lists in an efficient and easy manner. This problem is a part of data structures(Linked Lists). This problem was frequently asked in big tech company interviews, so now let's get into the problem and its optimized solution.
Now let's see what a linked list is and how it works along with its advantages.
What is a linked list?
- The linked list is a data structure that stores a linear collection of data elements, called nodes which are stored in memory at random locations.
- In the linked list, each node is divided into two parts.
- The first part contains the data of the element.
- The second part contains the address of the next node in the list.
Advantages of a linked list
- A linked list is a dynamic data structure, so it is easy to allocate and deallocate memory.
- No memory wastage.
- Insertion and deletion of elements are easier.
- Using a linked list one can implement sack and queue.
The problem is you will be given with two linked lists which are in sorted order, we have to merge these two linked lists into a fully sorted linked list.
Input - linkedlist 1: 2->3->4->6
linkedlist 2: 1->5->7->8
Output:- 1->2->3->4->5->6->7->8
Lets focus on the function mergelists():
- Function mergelists() has two parameters h1 and h2.
- h1 is a reference to the head of linked list 1.
- h2 is a reference to the head of linked list 2.
- Take a dummy node(temp) and initialize NULL to it.
- Now run a loop and compare the node values of both the linked lists.
- If the node value of one linked list is less than the node value of the other then assign the lesser node value to the temp node.
- Repeat these steps until any of the lists reached its end.
- Then merge the remaining nodes to the temp so that the output will be fully merged sorted linked list.
Program to merge two sorted linked lists-CPP
#include<iostream>
using namespace std;
class node{
public:
int data;
node *next;
};
void push(node **head,int val) //nodes are inserted at the front
{
node *new_node=new node();
new_node->data=val;
new_node->next=*head;
*head=new_node;
}
void print(node *head)
{
while(head)
{
cout<<head->data;
head=head->next;
}
}
node *mergelists(node *h1,node *h2)
{
node *temp=new node();
temp->data=0;
node *head=temp;
while(h1!=NULL && h2!=NULL)
{
if(h1->data < h2->data)
{
temp->next=h1;
h1=h1->next;
}
else{
temp->next=h2;
h2=h2->next;
}
temp=temp->next;
}
if(h1!=NULL)
{
temp->next=h1;
}
else{
temp->next=h2;
}
return head->next;
}
int main()
{
node *final_head=NULL;
node *head1=NULL;
node *head2=NULL;
//data is being added to the linked list 1.
push(&head1,6);
push(&head1,4);
push(&head1,3);
push(&head1,2);
//data is being added to the linked list 2.
push(&head2,8);
push(&head2,7);
push(&head2,5);
push(&head2,1);
final_head=mergelists(head1,head2);
print(final_head);
}
This code runs in O(n) time complexity as both the linked lists are traversed only once.
So, by understanding this program you will be clear with a linked list, and it's working and you will be able to merge two sorted linked lists.
if you like this article you can read our other article that can help you with data structures.
0 Comments