Merge two Sorted Linked Lists

21.Merge Two Sorted Lists

Linked List

Two Pointers

Problem Statement:

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists (i.e., modify the links in-place).

Example:

Input:

l1 = [1,2,4] l2 = [1,3,4]

→

Output:

[1,1,2,3,4,4]

Lists are merged by reusing the original nodes and updating their links.

Algorithm:

1. Create dummy node to handle edge cases and track result head
2. Compare nodes from both lists and link smaller value
3. Advance pointer in list where we took the node
4. Attach remaining nodes from non-empty list

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // Step 1: Create dummy node to avoid edge cases with empty lists
    ListNode dummy = new ListNode(0), curr = dummy;
    
    // Step 2: Compare and merge while both lists have nodes
    // Note: Using && since we're merging in place
    while (l1 != null && l2 != null) {
        // Step 3: Link the smaller value to result
        if (l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }

    // Step 4: Attach remaining nodes (if any)
    // Note: No iteration needed since we're reusing the original nodes
    if (l1 != null) curr.next = l1;
    if (l2 != null) curr.next = l2;

    return dummy.next;
}

Complexity:

Time: O(n + m) | Space: O(1)