Merge Two Sorted Lists Visualizer

list1.val < list2.val ?

lists row 1 = list1 · row 2 = list2 · row 3 = merged, hanging off the dashed dummy node

public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(); ListNode node = dummy; while (list1 != null && list2 != null) { if (list1.val < list2.val) { node.next = list1; list1 = list1.next; } else { node.next = list2; list2 = list2.next; } node = node.next; } node.next = list1 != null ? list1 : list2; // attach the rest return dummy.next;}

list1: —
list2: —
node: —
merged: —

Why it works

Brute force copies: collect every value, sort, and build a new list. O((m+n) log(m+n)) time and m+n new nodes.
The smallest remaining value is always one of the two heads, because both lists are sorted. Compare the heads, take the smaller, repeat. This is the merge step of merge sort.
The dummy node gives the merged list a fixed starting point, so the first node needs no special case. Return dummy.next, not dummy.
When one list runs out, attach the other in one assignment. It is already sorted and every value is at least the merged tail. Forgetting line 14 silently drops those nodes.
Nodes are relinked, not copied: O(m+n) time, O(1) extra space. A recursive version is shorter but uses O(m+n) call stack. On ties, <= instead of < keeps list1's node first (a stable merge); both are accepted.
Follow-up: Merge k Sorted Lists (LeetCode 23) keeps the k heads in a min-heap, or merges lists pairwise. O(N log k).