Merge Two Sorted Lists
Merge two sorted linked lists by reusing their nodes.
Why does this pattern fit?
Restate the exact job
Merge two sorted linked lists by reusing their nodes.
The smaller current head is the next globally smallest node.
O(n + m) time · O(1) space
Forgetting to advance the chosen cursor creates a cycle or infinite loop.
How to solve Merge Two Sorted Lists
The goal is to solve this problem from the pattern, not to memorize a finished answer. Use this as a check after your own attempt.
What the question asks
Merge two sorted linked lists by reusing their nodes.
Why Linked-list rewiring fits
The smaller current head is the next globally smallest node.
State to maintain
A dummy head, output tail, and two input cursors.
Transition
Attach the smaller node, advance that cursor, then append the remaining list.
Time and space
O(n + m) time · O(1) space
Counterexample to the tempting mistake
Forgetting to advance the chosen cursor creates a cycle or infinite loop.
Prove it again tomorrow
Close this page. Rebuild the state and transition from memory, write a test that exposes the mistake above, then solve a fresh input without looking back. A same-day reread is practice, not proof of retention.