See Also:
Example Program To Merge Two Singly Linked Lists:
C Program To Merge Two Arrays
C Program For Array Representation Of Sparse Matrix
C Program To Perform Insertion, Deletion, Searching & Traversal In Singly Linked List
C Program To Perform Insertion, Deletion, Sorting In Doubly Linked List - (Simple)
C Program To Sort A Doubly Linked List (Descending Order)
C Program To Reverse Linked List
C Program To Implement Circular Singly Linked List
C Program To Implement Circular Doubly Linked List
C Program For Polynomial Multiplication Using Linked List
C Program For Polynomial Addition Using Linked List
C Program For Linked List Representation Of Sparse Matrix
C Program To Concatenate Two Linked Lists
C Program To Perform Recursion On Linked List
C Program For Array Representation Of Sparse Matrix
C Program To Perform Insertion, Deletion, Searching & Traversal In Singly Linked List
C Program To Perform Insertion, Deletion, Sorting In Doubly Linked List - (Simple)
C Program To Sort A Doubly Linked List (Descending Order)
C Program To Reverse Linked List
C Program To Implement Circular Singly Linked List
C Program To Implement Circular Doubly Linked List
C Program For Polynomial Multiplication Using Linked List
C Program For Polynomial Addition Using Linked List
C Program For Linked List Representation Of Sparse Matrix
C Program To Concatenate Two Linked Lists
C Program To Perform Recursion On Linked List
Insertion, Deletion, Traversal, Reversal And Search Operation on Arrays
Doubly Linked List - Insertion, Traversal, Searching, Delete Node, Delete List
Doubly Linked List - Insertion, Traversal, Searching, Delete Node, Delete List
Example Program To Merge Two Singly Linked Lists:
#include<stdlib.h>
struct node {
int data;
struct node *next;
};
struct node *head1, *head2, *head3;
/*
* creates node and fill the given data
*/
struct node * createNode(int data) {
struct node *ptr = (struct node *) malloc(sizeof (struct node));
ptr->data = data;
ptr->next = NULL;
return ptr;
}
/* insert data into the list in ascending order */
void insert(struct node ** myNode, int data) {
struct node *xPtr, *yPtr, *zPtr = *myNode;
xPtr = createNode(data);
/* insert at the front of the list */
if (*myNode == NULL || (*myNode)->data > data) {
*myNode = xPtr;
(*myNode)->next = zPtr;
return;
}
/* insertion at the end or middle of the list */
while (zPtr) {
yPtr = zPtr;
zPtr = zPtr->next;
if (!zPtr) {
yPtr->next = xPtr;
break;
} else if ((data > yPtr->data) && (data < zPtr->data)) {
xPtr->next = zPtr;
yPtr->next = xPtr;
break;
}
}
return;
}
/* delete the given list */
struct node * deleteList(struct node *ptr) {
struct node *temp;
while (ptr){
temp = ptr->next;
free(ptr);
ptr = temp;
}
return NULL;
}
/* traverse the given list and print data in each node */
int walkList(struct node *ptr) {
int i = 0;
while (ptr) {
printf("%d ", ptr->data);
ptr = ptr->next;
i++;
}
return (i);
}
void mergeList(struct node *list1, struct node *list2, struct node **list3) {
struct node *ptr = NULL;
/* if both list are not present, then list3 will be NULL */
if (!list1 && !list2) {
printf("Both First and Second List are empty!!\n");
return;
}
/* both lists are available */
while (list1 && list2) {
if (*list3 == NULL) {
/* head node for list3 */
*list3 = (struct node *)calloc(1, sizeof (struct node));
ptr = *list3;
} else {
ptr->next = (struct node *)calloc(1, sizeof (struct node));
ptr = ptr->next;
}
if (list1->data < list2->data) {
/* insert data from list1 to list3 & advance list1*/
ptr->data = list1->data;
list1 = list1->next;
} else if (list1->data > list2->data) {
/* insert data from list2 to list3 & advance list2 */
ptr->data = list2->data;
list2 = list2->next;
} else {
/* insert data from list1 to list3 & advance both lists */
ptr->data = list1->data;
list1 = list1->next;
list2 = list2->next;
}
}
/* node left remain in list1 is inserted into list3 */
while (list1) {
ptr->next = (struct node *)calloc(1, sizeof(struct node));
ptr = ptr->next;
ptr->data = list1->data;
list1 = list1->next;
}
/* nodes left remain in list2 is inserted into list3 */
while (list2) {
ptr->next = (struct node *)calloc(1, sizeof(struct node));
ptr = ptr->next;
ptr->data = list2->data;
list2 = list2->next;
}
return;
}
int main (int argc, char *argv[]) {
int data, i, n;
FILE *fp1, *fp2;
fp1 = fopen(argv[1], "r");
fp2 = fopen(argv[2], "r");
if (!fp1 || !fp2) {
printf("Unable to open file\n");
fcloseall();
exit(0);
}
while (fscanf(fp1, "%d", &data) != EOF) {
insert(&head1, data);
}
while (fscanf(fp2, "%d", &data) != EOF) {
insert(&head2, data);
}
printf("\nData in First Linked List:\n");
n = walkList(head1);
printf("\nNo of elements in linked list: %d\n", n);
printf("\n\nData in Second Linked List:\n");
n = walkList(head2);
printf("\nNo of elements in linked list: %d\n\n", n);
mergeList(head1, head2, &head3);
printf("\nData in Merged List:\n");
n = walkList(head3);
printf("\nNo of elements in merged list: %d\n\n", n);
head1 = deleteList(head1);
head2 = deleteList(head2);
head3 = deleteList(head3);
return 0;
}
Output: (Merging Two Singly Linked List - Example in C)
jp@jp-VirtualBox:~/$ cat input1.txt
1 3 5 7 9 11 13 15
jp@jp-VirtualBox:~/$ cat input2.txt
2 4 6 8 10 12 14 16
jp@jp-VirtualBox:~/$ ./a.out input1.txt input2.txt
Data in First Linked List:
1 3 5 7 9 11 13 15
No of elements in linked list: 8
Data in Second Linked List:
2 4 6 8 10 12 14 16
No of elements in linked list: 8
Data in Merged List:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
No of elements in merged list: 16
1 3 5 7 9 11 13 15
jp@jp-VirtualBox:~/$ cat input2.txt
2 4 6 8 10 12 14 16
jp@jp-VirtualBox:~/$ ./a.out input1.txt input2.txt
Data in First Linked List:
1 3 5 7 9 11 13 15
No of elements in linked list: 8
Data in Second Linked List:
2 4 6 8 10 12 14 16
No of elements in linked list: 8
Data in Merged List:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
No of elements in merged list: 16
No comments:
Post a Comment