C Program to Merge Two Linked Lists

Introduction

Merging two linked lists involves combining the elements of both lists into a single linked list. The merge operation can be done in two ways: appending the second list to the end of the first list or merging the lists in a sorted manner if both lists are already sorted.

Example:

• Input: Two linked lists with nodes containing [1, 3, 5] and [2, 4, 6].
• Output: The merged linked list will contain [1, 2, 3, 4, 5, 6].

Problem Statement

Create a C program that:

• Creates two singly linked lists.
• Merges the two linked lists into a single list.
• Displays the merged linked list.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output functions and dynamic memory allocation.
2. Define the Node Structure: Create a structure for the node containing an integer data part and a pointer to the next node.
3. Implement the Function to Merge Two Linked Lists: Write a function that merges two linked lists into a single list.
4. Implement the Functions to Insert Nodes at the End of the Linked List: Write functions to insert nodes at the end of each linked list.
5. Create a Main Function: In the main() function, create two linked lists, merge them, and display the result.

C Program to Merge Two Linked Lists

#include <stdio.h>
#include <stdlib.h>

// Step 2: Define the Node Structure
struct Node {
    int data;
    struct Node* next;
};

// Function to insert a node at the end of the linked list
void insertAtEnd(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    struct Node* last = *head_ref;

    new_node->data = new_data;
    new_node->next = NULL;

    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    while (last->next != NULL) {
        last = last->next;
    }

    last->next = new_node;
}

// Function to merge two linked lists
struct Node* mergeLists(struct Node* head1, struct Node* head2) {
    struct Node* mergedHead = NULL;
    struct Node** lastPtrRef = &mergedHead;

    while (head1 != NULL && head2 != NULL) {
        if (head1->data <= head2->data) {
            *lastPtrRef = head1;
            head1 = head1->next;
        } else {
            *lastPtrRef = head2;
            head2 = head2->next;
        }
        lastPtrRef = &((*lastPtrRef)->next);
    }

    if (head1 != NULL) {
        *lastPtrRef = head1;
    } else {
        *lastPtrRef = head2;
    }

    return mergedHead;
}

// Function to display the linked list
void displayList(struct Node* node) {
    while (node != NULL) {
        printf("%d -> ", node->data);
        node = node->next;
    }
    printf("NULL\n");
}

int main() {
    struct Node* head1 = NULL;
    struct Node* head2 = NULL;
    struct Node* mergedHead = NULL;

    // Insert elements into the first linked list
    insertAtEnd(&head1, 1);
    insertAtEnd(&head1, 3);
    insertAtEnd(&head1, 5);

    // Insert elements into the second linked list
    insertAtEnd(&head2, 2);
    insertAtEnd(&head2, 4);
    insertAtEnd(&head2, 6);

    // Display the first linked list
    printf("First Linked List: ");
    displayList(head1);

    // Display the second linked list
    printf("Second Linked List: ");
    displayList(head2);

    // Merge the two linked lists
    mergedHead = mergeLists(head1, head2);

    // Display the merged linked list
    printf("Merged Linked List: ");
    displayList(mergedHead);

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Node Structure

• The Node structure contains two members: an integer data to store the node’s data, and a pointer next to point to the next node in the list.

Function to Insert a Node at the End of the Linked List

• The insertAtEnd function takes a double pointer to the head of the linked list (head_ref) and the data to be inserted (new_data).
• A new node is allocated dynamically using malloc().
• If the linked list is empty, the new node becomes the head of the list.
• Otherwise, the function traverses the list to the last node and updates the last node’s next pointer to point to the new node.

Function to Merge Two Linked Lists

• The mergeLists function takes pointers to the heads of two linked lists (head1 and head2) and returns a pointer to the head of the merged linked list.
• The function compares the data in the nodes of the two lists, adding the smaller element to the merged list.
• The lastPtrRef pointer is used to keep track of the last node in the merged list, allowing new nodes to be appended as the lists are merged.
• If one list is exhausted before the other, the remaining nodes of the non-exhausted list are appended to the merged list.

Function to Display the Linked List

• The displayList function traverses the linked list from the head and prints each node’s data, followed by an arrow (->), until it reaches the end (NULL).

Main Function

• The main function creates two linked lists by inserting nodes at the end using the insertAtEnd function.
• It then displays both linked lists, merges them using the mergeLists function, and displays the merged list.

Output Example

Example Output:

First Linked List: 1 -> 3 -> 5 -> NULL
Second Linked List: 2 -> 4 -> 6 -> NULL
Merged Linked List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

Conclusion

This C program demonstrates how to merge two linked lists. It covers basic concepts such as dynamic memory allocation, pointer manipulation, and linked list traversal, making it a useful example for beginners learning data structures in C programming.