Merge two sorted linked lists

Given the head of two sorted linked lists consisting of nodes respectively. The task is to merge both lists and return the head of the sorted merged list.

Examples:

Input: head1 = 5 -> 10 -> 15 -> 40, head2 = 2 -> 3 -> 20
Output: 2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40
Explanation:

Input: head1 = 1 -> 1, head2 = 2 -> 4
Output: 1 -> 1 -> 2 -> 4
Explanation:

Constraints:
1 <= no. of nodes<= 10³
0 <= node->data <= 10⁵

Approach 01:

class Solution {
public:
    Node* sortedMerge(Node* list1, Node* list2) {
        Node dummyNode(0);  // Dummy node to simplify edge cases
        Node* mergedList = &dummyNode;  // Pointer to construct the merged list

        // Merge the two lists while both have nodes remaining
        while (list1 && list2) {
            if (list1->data <= list2->data) {
                mergedList->next = list1;
                list1 = list1->next;
            } else {
                mergedList->next = list2;
                list2 = list2->next;
            }
            mergedList = mergedList->next;
        }

        // Append any remaining nodes from list1 or list2
        if (list1)
            mergedList->next = list1;
        if (list2)
            mergedList->next = list2;

        return dummyNode.next;  // Return the merged list, skipping the dummy node
    }
};

class Solution:
    def sortedMerge(self, list1, list2):
        dummyNode = Node(0)  # Dummy node to simplify edge cases
        mergedList = dummyNode  # Pointer to construct the merged list
        
        # Merge the two lists while both have nodes remaining
        while list1 and list2:
            if list1.data <= list2.data:
                mergedList.next = list1
                list1 = list1.next
            else:
                mergedList.next = list2
                list2 = list2.next
            mergedList = mergedList.next
        
        # Append any remaining nodes from list1 or list2
        if list1:
            mergedList.next = list1
        if list2:
            mergedList.next = list2
        
        return dummyNode.next  # Return the merged list, skipping the dummy node

Time Complexity:

• Traversing Both Lists:

  Each node in list1 and list2 is visited exactly once during the merging process. If the lengths of list1 and list2 are \( n \) and \( m \), respectively, this step takes \( O(n + m) \).

• Overall Time Complexity:

  The total time complexity is \( O(n + m) \).

Space Complexity:

• Auxiliary Space:

  The solution operates in-place and does not use any additional memory apart from a few pointers. Thus, the auxiliary space complexity is \( O(1) \).

• Overall Space Complexity:

  The total space complexity is \( O(1) \).