Zip two sorted lists together

Given two sorted linked lists, splice them into one sorted list and return its head.

Worked example#

For 1 -> 2 -> 4 and 1 -> 3 -> 4, take the smaller head each time:

The answer is 1 1 2 3 4 4.

When one list runs out, the other is already sorted and already correct, so it can be attached whole rather than walked node by node.

The trick worth learning#

Building a list front to back means the first node is a special case: there is nothing to attach it to yet. Writing if (head == null) head = node; else tail.next = node; inside the loop works and is noisy.

Instead start with a dummy node that you throw away at the end. Every real node then has something to attach to, the loop has no special case, and the answer is dummy.next.

That trick is worth knowing because it applies to almost every problem that builds a linked list.

The cost#

Time O(n + m), one pass over each. Memory O(1), because no node is copied: the existing nodes are relinked.

Constraints#

• 0 <= nodes in each list <= 5000
• -1000 <= value <= 1000
• Both lists are sorted in non-decreasing order