Merge Two Sorted Lists - A Simple Approach to Merge Two Sorted Linked Lists

Problem Statement

Given the heads of two sorted linked lists list1 and list2, merge the two lists into one sorted list. The merged list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

Iterative Approach

1. Create an empty linked list list3 and a pointer curr to traverse through the linked list.

2. Compare the first nodes of list1 and list2, add the smaller value to list3 and move the pointer of that list to the next node.

3. Continue the above step until either list1 or list2 becomes null.

4. If any of the lists still have nodes, add those nodes to list3.

5. Return the head of list3.

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == NULL) {
            return list2;
        }
        if (list2 == NULL) {
            return list1;
        }
        ListNode* list3 = new ListNode();
        ListNode* curr = list3;
        // The first node is initialized with 0 value
        // change the first node
        if (list1->val <= list2->val) {
            curr->val = list1->val;
            list1 = list1->next;
        } else {
            curr->val = list2->val;
            list2 = list2->next;
        }
        // append merged sorted list until n-2 size
        while (list1 != NULL && list2 != NULL) {
            if (list1->val <= list2->val) {
                curr->next = new ListNode(list1->val);
                list1 = list1->next;
            }
            else {
                curr->next = new ListNode(list2->val);
                list2 = list2->next;
            }
            curr = curr->next;
        }
        // append last element
        if (list1 != NULL) {
            curr->next = list1;
        }
        if (list2 != NULL) {
            curr->next = list2;
        }
        return list3;
    }

Recursive Approach

1. Check if either of the given linked lists is null, return the other list.

2. Compare the first nodes of the two linked lists.

3. Assign the smaller value node as the next to the current node and move the pointer of that list to the next node.

4. Continue the above step until either list1 or list2 becomes null.

5. If any of the lists still have nodes, add those nodes to the next to the current node.

6. Return the head of the linked list.

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
       if(l1 == NULL)
            return l2;

        if(l2 == NULL)
            return l1;

        if(l1 -> val <= l2 -> val)
        {
            l1 -> next = mergeTwoLists(l1 -> next, l2);
            return l1;
        }

        else
        {
            l2 -> next = mergeTwoLists(l1, l2 -> next);
            return l2;            
        }
}

Time Complexity

Both the iterative and recursive approaches have the same time complexity of O(n + m), where n and m are the lengths of the two input linked lists.

This is because we need to traverse through each node of the linked lists to merge them.

Space Complexity

The iterative approach has a space complexity of O(1) as we are only using a constant amount of extra space for the list3 and curr pointers.

The recursive approach has a space complexity of O(n + m) due to the recursive calls that are made for each node in the linked lists.

Conclusion

Both the iterative and recursive approaches have the same time complexity of O(n + m), but the iterative approach has a lower space complexity of O(1) compared to the recursive approach with O(n + m).

LeetCode: Merge Two Sorted Lists