How to Merge Two Sorted Linked Lists in C++

To merge two sorted linked lists in C++, use a pointer to compare nodes from both lists and build a new sorted list by linking nodes in order. This can be done by iterating through both lists, choosing the smaller node each time, and connecting it to the merged list using ListNode pointers.

Syntax

The function to merge two sorted linked lists typically takes two pointers to the heads of the lists and returns a pointer to the head of the merged sorted list.

Each node is represented by a ListNode struct or class with a value and a pointer to the next node.

cpp

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2);

Example

This example shows how to merge two sorted linked lists by comparing their nodes and linking them in sorted order. It creates two lists, merges them, and prints the result.

cpp

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); // Temporary start node
    ListNode* tail = &dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // Attach the remaining nodes
    tail->next = l1 ? l1 : l2;

    return dummy.next;
}

void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << "\n";
}

int main() {
    // List 1: 1 -> 3 -> 5
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(3);
    l1->next->next = new ListNode(5);

    // List 2: 2 -> 4 -> 6
    ListNode* l2 = new ListNode(2);
    l2->next = new ListNode(4);
    l2->next->next = new ListNode(6);

    ListNode* merged = mergeTwoLists(l1, l2);
    printList(merged); // Output: 1 2 3 4 5 6 

    return 0;
}

Output

1 2 3 4 5 6 

Common Pitfalls

• Not handling the case when one list is empty, which can cause null pointer errors.
• Forgetting to link the remaining nodes after one list ends.
• Modifying the input lists incorrectly, causing loss of nodes.
• Not using a dummy node can make the code more complex and error-prone.

cpp

/* Wrong way: Missing attaching remaining nodes */
ListNode* mergeWrong(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    // Missing tail->next = l1 or l2 here
    return dummy.next;
}

/* Correct way: Attach remaining nodes */
ListNode* mergeCorrect(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

Quick Reference

• Use a dummy node to simplify list merging.
• Compare nodes from both lists and link the smaller one.
• Attach remaining nodes after one list ends.
• Return the next node of dummy as the merged list head.

Key Takeaways

Use a dummy node to simplify merging two sorted linked lists.

Always attach the remaining nodes after one list is fully traversed.

Compare nodes one by one and link the smaller to the merged list.

Handle empty lists gracefully to avoid null pointer errors.