Merge Two Sorted Lists
The shape of the problem
Merge two sorted linked lists into one sorted linked list, reusing the existing nodes (no new allocation beyond a dummy head).
Signals to notice
Brute force first
Dump all values into an array, sort, build a new list. O((m+n) log(m+n)) time and O(m+n) extra — ignores the sorted inputs.
The key insight
Because both inputs are sorted, the next node of the merged list is always the smaller of the two current heads. You never have to look further ahead than one node on each side.
Trace it on l1=1→3→5, l2=2→4
tail→dummy l1=1, l2=2 → 1 < 2 → tail.next=l1, tail=l1, l1=3 l1=3, l2=2 → 2 < 3 → tail.next=l2, tail=l2, l2=4 l1=3, l2=4 → 3 < 4 → tail.next=l1, tail=l1, l1=5 l1=5, l2=4 → 4 < 5 → tail.next=l2, tail=l2, l2=null l1 non-empty → tail.next=l1 (=5) return dummy.next: 1→2→3→4→5
What must stay true
The nodes reachable from `dummy.next` are a sorted prefix of the final answer, and the remaining nodes in l1 and l2 are all ≥ `tail.val`.
Shape of the loop
dummy = Node(0); tail = dummy while l1 and l2: if l1.val <= l2.val: tail.next = l1; l1 = l1.next else: tail.next = l2; l2 = l2.next tail = tail.next tail.next = l1 if l1 else l2 return dummy.next
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Forgetting the final append of the non-empty list. Without it, the merged output truncates at the first exhausted input and drops all trailing elements of the other list.