DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)
Linked List in C- Merge two Linked List into Single Linked List – Efficient :
Input
Linked List 1: one->three->five->seven
Head of Linked List 1 is head1
Linked List 2: two->four->six
Head of Linked List 2 is head2
Output
Linked List 3: one->two->three->four->five->six->seven
Head of Linked List 3 is head1
This program works irrespective of size of the two input linked list.
Source Code :
#include<stdio.h> //Input //Linked List 1: one->three->five->seven //Head of Linked List 1 is head1 // //Linked List 2: two->four->six //Head of Linked List 2 is head2 // //Output //Linked List 3: one->two->three->four->five->six->seven //Head of Linked List 3 is head1 struct node { //Structure named node to store integer in variable data and a pointer variable which can store address location of next node int data; struct node *next; //Pointer variable next is a self referential pointer which stores the address of structure node }; struct node *head1 = NULL; struct node *head2 = NULL; //Pointer head1 and head2 are the pointers which stores the address of two input linked list void merge() { //Function to merge the two input linked list struct node *temp1 = head1; struct node *temp2 = head2; //Use a new pointer variable temp1 and temp2 //Do not use the pointer variable head1 and head2 directly. If we use it, the address location of the first node in the two linked list will be lost 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) { //Executes until both temp1 and temp2 are not 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 print(struct node *temp) { //This funtion is used to print the data in each of the node in the linked list //Process of moving from one node to another node is called as traversing while(temp!=NULL) { printf("\n%d ",temp->data); temp=temp->next; } } int main() { 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 //Input //Linked List 1: one->three->five->seven //Head of Linked List 1 is head1 // //Linked List 2: two->four->six //Head of Linked List 2 is head2 // //Output //Linked List 3: one->two->three->four->five->six->seven //Head of Linked List 3 is head1 printf("\nBefore Merging"); printf("\nInput: Linked List 1"); print(head1); printf("\nInput: Linked List 2"); print(head2); merge(); //Merging the two linked list into single linked list printf("\nAfter Merging"); printf("\nOutput: Linked List 3"); print(head1); return 0; }
Output :
Before Merging Input: Linked List 1 // Head pointer of first linked list is head1 1 3 5 7 Input: Linked List 2 // Head pointer of second linked list is head2 2 4 6 After Merging Output: Linked List 3 // Head pointer of output linked list is head1 1 2 3 4 5 6 7