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;
}

LANGUAGE:

DARK MODE: