C Program To Merge Two Linked Lists

Example Program To Merge Two Singly Linked Lists:

---

  #include<stdio.h>
  #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);
  }

  /* merge list1 and list2 to form list3 */
  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)

  1 3 5 7 9 11 13 15

  2 4 6 8 10 12 14 16
  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