- Write a C program to merge two sorted linked list into one linked list.
Given two linked list sorted in increasing order. We have to merge sorted linked lists and return a new single linked list which contains nodes of both linked list in increasing order.
For Example: First sorted Linked List 2 -- > 4 --> 6 --> 9 --> NULL Second sorted Linked List 1 --> 4 --> 5 --> 8 --> NULL Then, Merged Linked List 1 --> 2 --> 4 --> 4 --> 5 --> 6 --> 8 --> 9 --> NULL Singly linked list's node structure is as follows: struct node { int data; struct node *next; } Here, we will write a function "struct node* mergeLinkedList[struct node* LLOne, struct node* LLTwo]" which takes head pointer of two sorted linked list and return head pointer of merged linked list.C program to merge two sorted linked list
include #include /* A structure of linked list node */ struct node { int data; struct node *next; } *LLOne, *LLTwo, *mergedLL; void initialize[]{ LLOne = LLTwo = mergedLL = NULL; } /* Given a Inserts a node in front of a singly linked list. */ void insert[struct node **head, int num] { /* Create a new Linked List node */ struct node* newNode = [struct node*] malloc[sizeof[struct node]]; newNode->data = num; /* Next pointer of new node will point to head node of linked list */ newNode->next = *head; /* make new node as new head of linked list */ *head = newNode; printf["Inserted Element : %d\n", num]; } struct node* mergeLinkedList[struct node* LLOne, struct node* LLTwo]{ struct node *resultHead, *resultTail, *temp; resultHead = resultTail = NULL; while[1]{ /* */ if[LLOne == NULL]{ resultTail->next = LLTwo; break; } if[LLTwo == NULL] { resultTail->next = LLOne; break; } /* Check whether current node of which Linked list is smaller*/ if[LLOne->data data]{ temp = LLOne; LLOne = LLOne->next; } else { temp = LLTwo; LLTwo = LLTwo->next; } /*Add smaller node to result linked list */ if[resultHead == NULL]{ resultHead = resultTail = temp; } else { resultTail->next = temp; resultTail = temp; } resultTail->next = NULL; } return resultHead; } /* Prints a linked list from head node till tail node */ void printLinkedList[struct node *nodePtr] { while [nodePtr != NULL] { printf["%d", nodePtr->data]; nodePtr = nodePtr->next; if[nodePtr != NULL] printf["-->"]; } } int main[] { initialize[]; /* Creating First linked List*/ insert[&LLOne, 9]; insert[&LLOne, 6]; insert[&LLOne, 3]; insert[&LLOne, 1]; printLinkedList[LLOne]; printf["\n"]; /* Creating Second linked List*/ insert[&LLTwo, 10]; insert[&LLTwo, 6]; insert[&LLTwo, 5]; insert[&LLTwo, 2]; printLinkedList[LLTwo]; /* Merge Linked List */ mergedLL = mergeLinkedList[LLOne, LLTwo]; printf["\nMerged Linked List\n"]; printLinkedList[mergedLL]; return 0; } OutputInserted Element : 9 Inserted Element : 6 Inserted Element : 3 Inserted Element : 1 1-->3-->6-->9 Inserted Element : 10 Inserted Element : 6 Inserted Element : 5 Inserted Element : 2 2-->5-->6-->10 Merged Linked List 1-->2-->3-->5-->6-->6-->9-->10
Page 2
In this article, we will learn how to Merge two sorted linked list such that the final linked list is also sorted in linear time O[N].
Table of contents:
- Problem Statement: Merge two sorted linked lists
- Algorithm
- Implementation [Step by Step]
Let us get started with Merge two sorted linked lists.
Merge two given sorted linked list and return head of new linked list which should also be sorted.
Example :
Input: linked list 1 = {1,2,4} , linked list 2 = {1,3,4}
Output: {1,1,2,3,4,4}
Time Complexity :
O[n], beacuse of only one loop iterating only one time.
Algorithm
The steps to Merge two sorted linked lists are:
- Traverse both Linked Lists linearly from the first node
- Compare current nodes of both Linked List
- Delete the smaller node
- Insert the smaller node at the end of final Linked List
- If one Linked List is empty during processing, move all elements of the other sorted Linked List to the end of the final Linked List
- The final Linked List is the merged Linked List.
The implementation steps are:
1.First we define a node by either using struct or class. 2.Create a function to create new nodes. 3.Create a function which takes two sorted linked lists as input and return head of merged linkedlist.
4.Create a function to display the linked list and write main function.
Implementation [Step by Step]
We can do this by either using struct or class.
struct node{ int data; struct node* next; };or
class node{ public: int data; node* next; };Step 2 : Function to create a new node
node* newnode[int key] { struct node* temp = new node; temp->data = key; temp->next = NULL; return temp; }Approach :
-
Check if linked list 1 is empty return linked list 2 , or if linked list 2 is empty return linked list 1.
-
Create new head of the merged linked list by comparing both linked list first elements and choosing the smaller value beacuse we want to maintain the order [should be sorted].
-
Now, for rest of the elements compare them one by one in a while loop and maintain a new pointer which will keep storing the elements and thus a new sorted linked list will be formed.
-
In the end just check if any element is left in the linked lists, if yes then add them to the new merged linked list and return head of new linked list.
Working of Code :
Let us take an example :-
Input two linked lists -
List 1 = 1 -> 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = null
Compare first two nodes in both linked lists : [1,1] both are equal we can choose to add any of the two in the final_list and move head pointer of the choosen list, in this case we choose list 1 and move head pointer to next element
List 1 = 2 -> 4
List 2 = 1 -> 3 -> 5
final_list = 1
Compare first two nodes in both linked lists : [2,1] , 1 is smaller so add it to the final_list and move the pointer in list 2.
List 1 = 2 -> 4
List 2 = 3 -> 5
final_list = 1 -> 1
Compare the first two nodes in both linked lists : [2,3], 2 is smaller so add it to the final_list and move the pointer in list 1.
List 1 = 4
List 2 = 3 -> 5
final_list = 1 -> 1 -> 2
Compare the first two nodes in both linked lists : [4,3], 3 is smaller so add it to the final_list and move the pointer in list 2.
List 1 = 4
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3
Compare the last two nodes in both linked lists : [4,5], 4 is smaller so add it to the final_list and move the pointer in list 1.
List 1 = NULL
List 2 = 5
final_list = 1 -> 1 -> 2 -> 3 -> 4
If any one of the two linked lists is pointing to NULL then simply add all the elements of other list in final_list.
final_list = 1 -> 1 -> 2 -> 3 -> 4 -> 5
Note :
We are not deleting the elements of the two linked lists, but as we move the head pointer to the next element in linked list we already lost the previous element because we now don't have any means to go back to previous element, remember in a singly linked list only the address of next element is stored but not the previous one.
Implementation :
//function takes two linked lists as input node* merged_linkedlist[node* head1, node* head2] { //Check if any linked list is empty if [head1 == nullptr] { return head2; } else if [head2 == nullptr] { return head1; } //head pointer for merged linked list node* newhead = nullptr; //check for smallest element by comparing first two elements //of both linked lists if [head1->data data] { newhead = head1; //moving head 1 to point to next element in the //linked list 1 for further comparison head1 = head1->next; } else { newhead = head2; //moving head 2 to point to next element in the //linked list 2 for further comparison head2 = head2->next; } //new pointer to move forward and store new elements and //keeping head pointer of new linked list as it is node* temphead = newhead; //run the loop until we reach last element of both lists while [head1 != nullptr && head2 != nullptr] { node* temp = nullptr; if [head1->data data] { temp = head1; head1 = head1->next; } else { temp = head2; head2 = head2->next; } //store the next element and move forward to new node temphead->next = temp; temphead = temp; } //if any element is left then add it to final linked list if [head1 != nullptr] { temphead->next = head1; } else if [head2 != nullptr] { temphead->next = head2; } return newhead; }Step 4 : Main function and Display function
- Write a main function to call the merged_linkedlist function.
- Wrtie a display function to print merged linked list.