Merge two sorted Linked Lists

Given two sorted linked lists. We need to merge them and form a new linked list and the function should return pointer to head of the merged linked list

Example

Algorithm

Time complexity : O(n)

Step 1 : Create a function that takes two sorted linked lists and merge them.
Step 2 : Create a new empty linked list. Till one of the list or both are traversed add elements into the new linked list by comparing the head pointers.
a)    If head1-> data < head2-> data add head1->data to the linked list, and traverse pointer to next.
b)    If head2-> data < head2-> data add head2->data to the linked list, and traverse pointer to next.
c)     If list1 is traversed completely then just add the remaining list2 at the end of the new list and vice versa.
d)    simply copy the untraversed part of the list as it is already sorted.
Step 3 :  call the function for the given two sorted lists then it gives the final sorted list by merging both the lists.

Algorithm working Example

Given two linked lists a, b

We need to merge a, b

Step 1 : create a dummy node

Step 2 :  6 < 7 so, add 6

Step 3 :  7 < 8 so, add 7

Step 4 :  8 < 11 so, add 8

Step 5 :  11 < 12 so, add 11

Step 6 :  12 < 14 so, add 7

Step 7 :  Finally add 14, as it is the only 1 left.

C++ Program

#include <bits/stdc++.h>
using namespace std;

struct LL{
	int data;
	LL *next;	
};


void insertAtEnd(struct LL**head,int dataToBeInserted)
{
	
	struct LL*temp = *head;
	
	if(*head == NULL)
	{
		*head = new LL;
		(*head)->data = dataToBeInserted;
		(*head)->next = NULL;
	}
	
	else{
	
	while(temp->next!=NULL)
		temp=temp->next;
		
	temp->next=new LL;
	temp=temp->next;
	temp->data=dataToBeInserted;
	temp->next=NULL;
	}
	//O(number of nodes)
}

void sortedMerge(struct LL *&finalList,struct LL **head1 , struct LL **head2)
{
	struct LL *temp1 = *head1 , *temp2 = *head2;
	
	while(temp1 and temp2) //till one of the list or both lists are traversed
	{
		if(temp1->data <= temp2->data)
		{
			insertAtEnd(&finalList,temp1->data);
			temp1 = temp1->next;
		}
		else
		{
			insertAtEnd(&finalList,temp2->data);
			temp2 = temp2->next;
		}
	}
	
	while(temp1) //simply copy the untraversed part of the list as it is already sorted
	{
		insertAtEnd(&finalList,temp1->data);
		temp1 = temp1->next;
	}
	
	while(temp2) //simply copy the untraversed part of the list as it is already sorted
	{
		insertAtEnd(&finalList,temp2->data);
		temp2 = temp2->next;
	}
	
}

void display(struct LL**head)
{
	struct LL*temp=*head;
	while(temp!=NULL)
		{
			if(temp->next!=NULL)
			cout<<temp->data<<" ->";
			else
			cout<<temp->data;
			
			temp=temp->next; //move to next node
		}
		//O(number of nodes)
	cout<<endl;
}


int main()
{
	
	struct LL *head1 = NULL; //initial list has no elements
	insertAtEnd(&head1,6);
	insertAtEnd(&head1,16);
	insertAtEnd(&head1,25);
	insertAtEnd(&head1,50);
	insertAtEnd(&head1,79);
	insertAtEnd(&head1,96);
	
	cout <<"First list is :-\n";
	display(&head1);
	
	struct LL *head2 = NULL;
	insertAtEnd(&head2,2);
	insertAtEnd(&head2,36);
	insertAtEnd(&head2,55); //value changed from 15 to 25
	insertAtEnd(&head2,60);
	insertAtEnd(&head2,71);
	insertAtEnd(&head2,123);
	
	cout <<"\nSecond list is :-\n";
	display(&head2);
	
	struct LL *finalList = NULL;

	sortedMerge(finalList,&head1,&head2);
	
	cout <<"\nFinal sorted list is :-\n";
	display(&finalList);

	return 0;
}
Try It


Next > < Prev
Scroll to Top