Merge Two Sorted Linked Lists in C++

This C++ program demonstrates how to merge two sorted linked lists into a single sorted linked list. The implementation uses a simple linked list structure where each node contains an integer data and a pointer to the next node.

Program Code

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to merge two sorted linked lists
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) return l2;
    if (!l2) return l1;

    // Ensure that l1 is the list starting with the smaller element
    if (l1->val > l2->val) std::swap(l1, l2);

    // Start from the first list
    ListNode* result = l1;

    while (l1 != NULL && l2 != NULL) {
        ListNode* tmp = NULL;
        // Traverse the list until finding the place to insert elements from l2
        while (l1 != NULL && l1->val <= l2->val) {
            tmp = l1;
            l1 = l1->next;
        }
        // Now l1 is the first element greater than the current l2 element
        // Insert l2 here
        tmp->next = l2;
        std::swap(l1, l2);
    }

    return result;
}

// Helper function to print the linked list
void printList(ListNode* node) {
    while (node != NULL) {
        std::cout << node->val << " ";
        node = node->next;
    }
    std::cout << std::endl;
}

int main() {
    // Create first sorted linked list: 1->2->4
    ListNode* a = new ListNode(1);
    a->next = new ListNode(2);
    a->next->next = new ListNode(4);

    // Create second sorted linked list: 1->3->4
    ListNode* b = new ListNode(1);
    b->next = new ListNode(3);
    b->next->next = new ListNode(4);

    // Merge the lists
    ListNode* mergedList = mergeTwoLists(a, b);
    std::cout << "Merged List: ";
    printList(mergedList);

    return 0;
}

Explanation of the Code

The program includes a struct definition for the linked list node, which consists of an integer value and a pointer to the next node. The function mergeTwoLists() takes two sorted linked lists and merges them. It handles the cases where one of the lists is empty, ensuring stability and maintaining order.

The merging process checks each node and inserts nodes from the second list into the first list at the appropriate positions. This is done by adjusting pointers without creating new nodes, thus being memory efficient. The helper function printList() is used to display the merged list.

Conclusion

This C++ program efficiently merges two sorted linked lists using a simple and understandable algorithm. The approach ensures that no additional memory is allocated for the nodes, and the existing nodes are reused.