Problem #21: Merge Two Sorted Lists

Intuition & Strategy Breakdown

Use a dummy head node. Compare the current heads of both sorted lists, append the smaller node to the merged list, and advance the corresponding list pointer until one is exhausted.

Python Solution

def mergeTwoLists(list1, list2):
    dummy = ListNode(0)
    curr = dummy
    
    while list1 and list2:
        if list1.val <= list2.val:
            curr.next = list1
            list1 = list1.next
        else:
            curr.next = list2
            list2 = list2.next
        curr = curr.next
    
    curr.next = list1 or list2
    return dummy.next

Java Solution

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            curr.next = list1;
            list1 = list1.next;
        } else {
            curr.next = list2;
            list2 = list2.next;
        }
        curr = curr.next;
    }
    
    curr.next = (list1 != null) ? list1 : list2;
    return dummy.next;
}