merge linked lists Algorithm
The Merge Linked Lists algorithm is a popular technique used in computer science to combine two sorted linked lists into a single, sorted linked list. This algorithm is commonly employed in various applications such as merging data from different sources or merging sorted arrays. Linked lists are data structures that consist of nodes, each containing a data element and a reference to the next node in the sequence. The merge algorithm works by comparing the first elements of each linked list and selecting the smaller value to be part of the resulting merged list. The process is then repeated with the remaining elements in the linked lists until one of the lists is exhausted. At this point, the remaining elements from the other list are simply appended to the merged list, completing the process.
To implement the Merge Linked Lists algorithm, a new linked list is created to store the merged results. Two pointers are initialized, one for each input linked list, and they are used to traverse the lists and compare the elements. As the algorithm iterates through the input lists, the smaller element among the two pointed values is inserted into the merged list, and the corresponding pointer is advanced to the next element. This process is continued until one of the input lists is depleted, at which point the remaining elements from the other list are appended to the merged list. The time complexity of this algorithm is O(n), where n is the total number of elements in both input lists, as each element needs to be visited once when merging the lists. The space complexity is also O(n), as a new linked list needs to be created to store the merged result.
#include<stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
struct node *head1 = NULL;
struct node *head2 = NULL;
///// MAIN ALGORITHMIC FUNCTION to MERGE the two input linked lists ///////
void merge()
{
struct node *temp1 = head1;
struct node *temp2 = head2;
struct node *holder1 = NULL;
struct node *holder2 = NULL;
//Temporary pointer variables to store the address of next node of the two input linked list
while(temp1!=NULL && temp2!=NULL)
{
holder1 = temp1 -> next;
//Storing the address of next node of first linked list
temp1->next=temp2;
//Making the first node of first linked list point to first node of second linked list
if(holder1!=NULL) {
//Making the first node of second linked list point to second node of first linked list
holder2 = temp2 -> next;
temp2 -> next = holder1;
}
temp1=holder1;
temp2=holder2;
//Updating the address location of two pointer variables temp1 and temp2
}
}
void printlist(struct node *temp){
printf("%d",temp->data);
temp=temp->next;
while(temp!=NULL){
printf("->%d",temp->data);
temp=temp->next;
}
printf("\n");
}
int main()
{
// Linked List 1: 1->3->5->7 : Linked List 2: 2->4->6
// making lists
struct node *one = (struct node*)malloc(sizeof(struct node));
struct node *two = (struct node*)malloc(sizeof(struct node));
struct node *three = (struct node*)malloc(sizeof(struct node));
struct node *four = (struct node*)malloc(sizeof(struct node));
struct node *five = (struct node*)malloc(sizeof(struct node));
struct node *six = (struct node*)malloc(sizeof(struct node));
struct node *seven = (struct node*)malloc(sizeof(struct node));
//Seven nodes are created
head1=one;
head2=two;
//head1 points to first node of first linked list
//head2 points to first node of second linked list
one->data=1;
one->next=three;
two->data=2;
two->next=four;
three->data=3;
three->next=five;
four->data=4;
four->next=six;
five->data=5;
five->next=seven;
six->data=6;
six->next=NULL;
//Last node of second input linked list
seven->data=7;
seven->next=NULL;
//Last node of first input linked list
printf("Linked List 1: ");
printlist(head1);
printf("\nLinked List 2: ");
printlist(head2);
//Merging the two linked list into single linked list
merge();
printf("\nMerged Linked List: ");
printlist(head1); //list one has been modified
return 0;
}