21. Merge Two Sorted Lists

Intuition

To merge two sorted linked lists into one sorted list, we can utilize a pointer-based approach. Given that both list1 and list2 are already sorted, merging them involves comparing nodes from both lists and linking them in ascending order.

Approach

1. Initialization: Start with two pointers, merged_head and current, both initialized to None.
2. Comparative Merging: Compare the values of the heads of list1 and list2. Set merged_head to the smaller node, and move the respective list's pointer forward.
3. Iterative Merging: Continue comparing the current nodes of list1 and list2. Link the smaller node to current.next, and move current and the pointer of the smaller node forward.
4. Append Remaining Nodes: Once one list is exhausted, append the remaining nodes of the other list directly to current.next.
5. Return: Return merged_head, which now points to the head of the merged sorted list.

Complexity

Time Complexity:

O(m + n), where m and n are the lengths of list1 and list2, respectively. We iterate through both lists once.

Space Complexity**:

O(1), since we only use a constant amount of extra space for pointers and variables, not proportional to the input size.

Code

C++

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1)
            return list2;
        if (!list2)
            return list1;
        if (list1->val < list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

Python

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        if not list1:
            return list2
        if not list2:
            return list1
        if list1.val < list2.val:
            merged_head = list1
            list1 = list1.next
        else:
            merged_head = list2
            list2 = list2.next
        
        current = merged_head
        while list1 and list2:
            if list1.val < list2.val:
                current.next = list1
                list1 = list1.next
            else:
                current.next = list2
                list2 = list2.next
            current = current.next
        if list1:
            current.next = list1
        elif list2:
            current.next = list2
        
        return merged_head

Java

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;
        
        if (list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

JavaScript

var mergeTwoLists = function (list1, list2) {
    if (!list1)
        return list2;

    if (!list2)
        return list1;

    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);
        return list1;
    }
    else {
        list2.next = mergeTwoLists(list1, list2.next);
        return list2;
    }
};