LeetCode 21: The Easy Merge That Still Fails Half of Interview Candidates

Hiring screens use a two-line problem to test pointer discipline and engineering judgment, so a miss on LeetCode 21 can cost an offer even when the candidate whiteboards DFS fluently. The split between iterative O(1) space and recursive O(m+n) stack depth maps directly to production decisions on data pipelines and long lists.

LeetCode 21 asks for merging two ascending linked lists in place, splicing the original nodes rather than copying values. The iterative solution with a dummy sentinel head is the engineering default: a `cur` tail pointer walks both lists, appending the smaller head, then grafts the remaining segment with one statement. That yields O(m+n) time and O(1) extra space and eliminates the special-case branch for the result head. The recursive version is far shorter, but each call consumes a stack frame, so depth equals merged list length; beyond roughly 100k nodes it triggers a StackOverflowError under default JVM stack sizing.

Most interview failures don't come from missing the algorithm. They come from pointer-order mistakes: writing `while (l1 != null || l2 != null)` then dereferencing null inside, forgetting to advance the tail pointer, using `<` instead of `<=` and losing stable ordering for equal values, or returning the dummy node itself so the answer grows a phantom -1. The correct sequence is fixed: attach `cur.next`, advance the selected list node, then advance `cur`, and finish by splicing the remaining non-empty list whole.

The same dummy-node pattern scales straight to the LeetCode 23 K-way merge: push the K list heads into a min-heap keyed by value, pop one, append it, and push its successor. Complexity drops from O(k·N) with sequential pairwise merging to O(N log k). Interviewers also ask about de-duplication, descending lists, and whether values may be copied into new nodes, so the follow-up set is nearly as valuable as the core implementation.