Merge Two Sorted Lists easy

Problem Statement

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

Example 1

• Input: list1 = [1,2,4], list2 = [1,3,4]
• Output: [1,1,2,3,4,4]

Example 2

• Input: list1 = [], list2 = []
• Output: []

Steps

1. Handle Empty Lists: Check if either list1 or list2 is empty. If so, return the non-empty list or an empty list if both are empty.

2. Create a Dummy Node: Create a dummy node to simplify the merging process. This dummy node will point to the head of the merged list.

3. Initialize Pointers: Initialize three pointers:

   • tail: Points to the current tail of the merged list (initially the dummy node).
   • p1: Points to the current node of list1.
   • p2: Points to the current node of list2.

4. Iterative Merging: Iterate while both p1 and p2 are not null:

   • Compare the values at p1 and p2.
   • Append the smaller node to the tail of the merged list and advance the corresponding pointer (p1 or p2).
   • Move the tail pointer to the newly appended node.

5. Append Remaining Nodes: After one of the lists is exhausted, append the remaining nodes from the other list to the tail of the merged list.

6. Return the Merged List: Return the next node after the dummy node (which is the head of the merged list).

Explanation

The algorithm efficiently merges two sorted linked lists by iteratively comparing the values of the current nodes in each list. The smaller value is always appended to the merged list, ensuring the resulting list remains sorted. The use of a dummy node simplifies the handling of the head of the merged list, eliminating the need for special cases.

Code

#include <iostream>

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

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode(0); // Create a dummy node
    ListNode* tail = dummy;

    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            tail->next = list1;
            list1 = list1->next;
        } else {
            tail->next = list2;
            list2 = list2->next;
        }
        tail = tail->next;
    }

    // Append remaining nodes from list1 or list2
    tail->next = (list1 != nullptr) ? list1 : list2;

    return dummy->next; // Return the head of the merged list
}

int main() {
    // Example usage:
    ListNode* list1 = new ListNode(1, new ListNode(2, new ListNode(4)));
    ListNode* list2 = new ListNode(1, new ListNode(3, new ListNode(4)));

    ListNode* mergedList = mergeTwoLists(list1, list2);

    while (mergedList != nullptr) {
        std::cout << mergedList->val << " ";
        mergedList = mergedList->next;
    }
    std::cout << std::endl; // Output: 1 1 2 3 4 4

    return 0;
}

Complexity

• Time Complexity: O(m + n), where 'm' and 'n' are the lengths of list1 and list2 respectively. We iterate through each list once.
• Space Complexity: O(1). We use a constant amount of extra space, regardless of the input size. The space used by the dummy node and pointers is constant.