Merge Two Sorted Lists: the idea to remember.

The core insight

Use a dummy head and repeatedly append the smaller current node, then append the remaining suffix.

Why it works

The chosen smaller frontier is no larger than any unconsumed node, so the output prefix stays sorted.

The mistake to avoid

Advance the output tail after attaching each node. The input nodes are reused and their links may change.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = a != null ? a : b;
    return dummy.next;
}

Make the next connection