Merge two sorted linked lists

Question

You are given the heads of two singly linked lists, each already sorted ascending. Merge them into one sorted list by splicing the existing nodes together (do not allocate new nodes for the payloads) and return the new head.

l1: 1 -> 2 -> 4
l2: 1 -> 3 -> 4
->  1 -> 1 -> 2 -> 3 -> 4 -> 4

Target $O(m + n)$ time and $O(1)$ extra space.

Accepted Answer

Keep a dummy node so the result has a stable anchor, and a tail pointer marking where the next node attaches. At each step compare the two front nodes, splice the smaller one onto tail, and advance that list. When one list runs out, the other is already sorted, so attach it wholesale. Tracing the example: we emit 1 (from l1), then 1 (from l2), then 2, 3, 4 (from l1), and finally attach the trailing 4 from l2, giving 1 1 2 3 4 4. Using <= rather than < keeps equal values in their original relative order (a stable merge). Time O(m + n); space O(1), we only relink existing nodes. Two natural fol…

Merge two sorted linked lists

Your answer

More Coding questions