Merge Two Sorted Linked Lists in C

This program demonstrates how to merge two sorted linked lists into a single sorted linked list using the C programming language. The approach ensures that the resulting list maintains the order of elements as they appeared in the individual lists.

Program Explanation

The program defines a linked list node structure with an integer data field and a pointer to the next node. Functions are provided to insert new nodes into a linked list, merge two sorted linked lists, and display the contents of a linked list.

• struct Node: Represents the structure of each node in the linked list.
• insertNode: Inserts a new node in the linked list while maintaining the sorted order.
• mergeLists: Merges two sorted linked lists into one sorted linked list.
• printList: Displays the contents of the linked list.

Source Code

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

struct Node {
    int data;
    struct Node* next;
};

// Function to create a new node
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Function to insert a new node in a sorted linked list
void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = newNode(new_data);
    struct Node* current;
    // Special case for the head end
    if (*head_ref == NULL || (*head_ref)->data >= new_data) {
        new_node->next = *head_ref;
        *head_ref = new_node;
    } else {
        // Locate the node before the point of insertion
        current = *head_ref;
        while (current->next != NULL && current->next->data < new_data) {
            current = current->next;
        }
        new_node->next = current->next;
        current->next = new_node;
    }
}

// Function to merge two sorted linked lists
struct Node* mergeLists(struct Node* head1, struct Node* head2) {
    struct Node dummy;
    struct Node* tail = &dummy;
    dummy.next = NULL;

    while (1) {
        if (head1 == NULL) {
            tail->next = head2;
            break;
        } else if (head2 == NULL) {
            tail->next = head1;
            break;
        }
        if (head1->data <= head2->data) {
            tail->next = head1;
            head1 = head1->next;
        } else {
            tail->next = head2;
            head2 = head2->next;
        }
        tail = tail->next;
    }
    return dummy.next;
}

// Function to print nodes in a given linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\\n");
}

int main() {
    struct Node* res = NULL;
    struct Node* a = NULL;
    struct Node* b = NULL;

    insertNode(&a, 5);
    insertNode(&a, 2);
    insertNode(&a, 3);
    printf("List A: ");
    printList(a);

    insertNode(&b, 4);
    insertNode(&b, 1);
    insertNode(&b, 6);
    printf("List B: ");
    printList(b);

    res = mergeLists(a, b);

    printf("Merged List: ");
    printList(res);

    return 0;
}
        

Conclusion

This C program effectively merges two sorted linked lists into a single sorted linked list. It utilizes simple but effective pointer manipulation to ensure that the merged list remains sorted without creating any additional nodes beyond those already present in the original lists.