Merge Two Sorted Lists
Merge Two Sorted Lists
Merge two sorted linked lists and return the head of the merged sorted list.
Why this is worth learning
The next smallest remaining value must be one of the two heads. Splicing existing nodes avoids allocating a second list while a dummy head removes the first-node special case.
Before coding: one-minute experiment
When the two current heads both hold 2, does selecting either invalidate sortedness?
Function signature
func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode
Inputs / outputs
l1,l2: heads of sorted linked lists.- Return: head of merged sorted list.
Example
1 -> 2 -> 4
1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Constraints
- 0 <= number of nodes <= 100_000
- Lists are sorted in non-decreasing order.
Core idea (near-solution)
Collecting all original pointers and sorting them is a correct baseline, but it ignores that each remaining input is already sorted. Its head is its smallest remaining value, so the next output must be one of the two heads. Selecting the smaller one cannot strand a smaller value behind it. Advance only the selected input and retain the output tail for the next link. A dummy gives that tail a useful initial value before any real node is selected. Equal heads allow either choice; sorting alone does not require a fixed cross-list tie order.
Invariant: the merged list so far is sorted.
Algorithm (step-by-step)
- Initialize a dummy node and a tail pointer.
- While both lists are non-empty:
- Append the smaller node to the tail.
- Advance the corresponding list.
- Append the remaining nodes.
- Return
dummy.Next.
Correctness sketch
The built prefix is sorted and contains exactly the nodes already removed from the two input prefixes; tail identifies its last node. Since each remainder is sorted, the smaller current head is no greater than any other remaining node. Linking that node after tail therefore extends the correct sorted prefix and consumes it once. When one remainder is empty, the other is already sorted and no smaller than the built prefix, so it can be attached wholesale. Every original node is included exactly once and no result-data node is allocated. The returned dummy.Next is the first real node.
Trace (hand walkthrough)
Example input:
1 -> 2 -> 4
1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
Walk:
- pick 1 (list1), then 1 (list2)
- next pick 2 (list1), then 3 (list2)
- append remaining 4 (list1), 4 (list2) -> 1->1->2->3->4->4
Pitfalls to avoid
- Forgetting to attach the remaining tail.
Debugging lens
Test nil on either side, equal values, and alternating small values. Verify result node identities and termination, not only the value sequence; accidental cycles can otherwise hide behind a bounded printout.
Complexity
- Time:
O(n+m) - Extra space:
O(1)(reusing nodes).
Implementation notes (Go)
- Use a dummy head and tail pointer to simplify merging.
- Attach the remaining list when one side is exhausted.
Contract precision
The two inputs are finite sorted lists with disjoint node ownership. The result reuses and rewires those nodes; callers must not expect the original next-pointer chains to remain intact.
Reconstruction checkpoint
Input nodes A(1)→B(3) and C(1)→D(2) have distinct identities. Give two valid identity orders after merging. What would a test miss if it checked only [1,1,2,3]?
Model answer
A→C→D→B and C→A→D→B are both sorted and contain each original node once. Values alone would accept newly allocated replacements, duplicated/missing equal-valued nodes, or mutations that keep the output values plausible. Check identities, original payloads, and termination without imposing a cross-input tie order.