GFG PTOD | 20 Jan 2025 | Merge two sorted linked lists

Iterative Solution : TC = O(m+n), SC = O(1)

Node* sortedMerge(Node* head1, Node* head2) {
        // code here
        //Iterative
        Node* temp;
        if(head1 == NULL) return head2;
        if(head2 == NULL) return head1;
        
        if(head1->data <= head2->data) {
            temp = head1;
            head1=head1->next;
        } else {
            temp = head2;
            head2 = head2->next;
        }
        
        Node* newHead = temp;
        
        while(head1 && head2) {
            if(head1->data <= head2->data) {
                temp->next = head1;
                head1=head1->next;
            } else {
                temp->next = head2;
                head2 = head2->next;
            }
            temp = temp->next;
        }
        
        if(head1) temp->next = head1;
        if(head2) temp->next = head2;
        
        return newHead;
    }

Recursive Solution : TC = O(m+n), SC = O(1)

Node* sortedMerge(Node* head1, Node* head2) {
        // code here
        // Recursive
        if(head1 == NULL) return head2;
        if(head2 == NULL) return head1;
        
        if(head1->data <= head2->data) {
            head1->next = sortedMerge(head1->next, head2);
            return head1;
        } else {
            head2->next = sortedMerge(head1, head2->next);
            return head2;
        }
    }