Merge sorted lists: splice only a safe frontier

Constructed practice problem; no company attribution. Prerequisites: reversing node links and cycle detection.

Candidate brief

THE PROBLEM

Two independently owned task queues are sorted by integer priority. Merge them into one sorted queue using the existing nodes. Preserve order inside each input, and prefer the first queue on equal priorities. What happens if the two inputs unexpectedly share a tail?

Write this:

@dataclass(eq=False)
class Node:
    value: object
    next: "Node | None" = None

def merge_sorted_lists(first, second):
    ...

Contract	Decision
Input	Two acyclic, node-disjoint `Node` chains with nondecreasing integer values; bool excluded
Output	Head of one merged chain using exactly all original node identities
Boundaries	Empty chains allowed; ties take first-chain nodes first; links intentionally mutate
Invalid input	Malformed links, cycles, unsorted/noninteger values, or shared nodes raise `ValueError` before mutation
Excluded	Persistent input chains and concurrent access during splicing

Optional refresher · the underlying tool

Merging two linked lists is a pointer operation. A dummy head is a temporary node before the output, so the first real append uses the same code as every later append:

dummy = Node(0)
tail = dummy
# After choosing one input node:
tail.next = chosen
tail = tail.next

Given 1 → 4 and 2 → 3, the output is 1 → 2 → 3 → 4. Keep the unchosen input suffix reachable; decide how equal values are ordered and whether old nodes may be reused.

A design choice worth saying aloud

The dummy node owns only the output assembly point; decide whether you splice the original nodes or allocate copies. Splicing is O(1) extra space but mutates input links, so callers must permit it. On equal keys, taking from the left first preserves a predictable cross-list tie policy.

What the interviewer expects

The interviewer gives you the scenario and the contract above. Explain what a successful call returns, walk through one example below, and name what your state means before choosing a data structure.

Done means: Head of one merged chain using exactly all original node identities.

Now predict each output before looking at the reference; invalid input should leave any existing state unchanged unless the contract says otherwise.

Test-case scenarios to settle before coding

01 · Representative

Input / starting state: 1→3 and 1→2
Expected result: 1(first)→1(second)→2→3

What it is testing: The first chain wins equal-value ties.

02 · One empty

Input / starting state: None and 2→4
Expected result: the original second head

What it is testing: No replacement nodes are needed.

03 · Both empty

Input / starting state: None, None
Expected result: None

What it is testing: The frontier can be empty on both sides.

04 · Duplicates

Input / starting state: 1→1 and 1
Expected result: all identities retained stably

What it is testing: Multiplicity and stable ties matter.

05 · Shared node

Input / starting state: two inputs converge on one object
Expected result: ValueError before mutation

What it is testing: Splicing shared ownership can create corruption.

06 · Unsorted/malformed

Input / starting state: a descending link or cycle
Expected result: ValueError before mutation

What it is testing: Validate the whole reachable inputs.

For each case, show which branch or state change produces that result.

For identities a1(1) → a2(3) and b1(1) → b2(2), return a1 → b1 → b2 → a2 → None. merge_sorted_lists(None, b1) is b1 when that chain is valid. Supplying the same nonempty head twice raises ValueError.

Before opening the explanation, restate the contract, trace the smallest useful example, implement a baseline, and identify the repeated work. Then implement your improvement independently and derive tests from the contract. Say what your state means before saying which data structure stores it.

Worked lesson, changed requirements, and reference

Define which links are final and which remain a frontier

A baseline collects node references from both chains, stably sorts by value, then reconnects them: O((n+m) log(n+m)) time and O(n+m) auxiliary space. Reading all first-chain nodes before second-chain nodes makes a stable sort honor the tie policy. But both inputs already expose their smallest remaining value at the head, so a two-way merge can avoid sorting and reference storage.

Remaining A	Remaining B	Choose	Logical output prefix
a1(1), a2(3)	b1(1), b2(2)	a1: first-chain tie	a1
a2(3)	b1(1), b2(2)	b1	a1, b1
a2(3)	b2(2)	b2	a1, b1, b2
a2(3)	empty	append A suffix	a1, b1, b2, a2

Maintain a dummy node and tail of the chosen prefix. Every chosen node is in sorted stable order; both input references head sorted unconsumed suffixes; tail is the only output position whose next link is not final. Its next may still point into an old suffix until the next splice, so do not claim the physical prefix is already None-terminated. Compare current heads, save/advance the chosen input reference, attach that node after tail, and advance tail. The smaller head cannot have a larger unconsumed predecessor, establishing the next output value. When one input empties, the other suffix is already in order and can be attached whole. The dummy is not part of the returned chain.

Before mutation, validate each chain with cycle detection and a sortedness pass. Two nonempty acyclic singly linked chains share any node exactly when their final node is the same object: after an intersection their next links are identical. Comparing tails therefore rejects aliasing with constant space. Without this check, splicing shared nodes can create a self-cycle. Validation plus merge takes O(n+m) time and O(1) auxiliary space; output reuses existing nodes. Node equality is identity-based, and values never decide whether objects are shared.

Follow-up 1: merge k sorted queues

Predict what replaces a two-head comparison. Keep one entry per nonempty queue in a min-heap, keyed by (value, queue_index) for deterministic cross-queue ties.

For N total nodes, merging costs O(N log k) time and O(k) frontier space, after validation. Cross-queue alias detection also needs a stated method; checking all tail pairs is quadratic in k, while a tail-identity set uses O(k) space.

Follow-up 2: consumers retain the original queues

Required observation	In-place splice effect	Changed approach
A reader follows a1.next expecting a2	merge changes it to b1	allocate new nodes or return an iterator of values
Caller requires old node identities in a new persistent chain	one next field cannot encode two chains	add separate link records or versioned indirection

A senior candidate tests tie stability by identity and catches shared-tail input before writes. A lead candidate defines transfer of ownership and whether readers need original identities, values, or snapshot order; that choice determines whether copying is a correct API migration or a broken contract.

Run and check

From the repository root:

cd curriculum/01-code/02-data-structures-algorithms/problems/16-merge-sorted-lists
python -m unittest -v test_solution.py

Reference implementation (download file, source below) · Contract and oracle tests (download file, source below). Read the tests after your attempt. A green reference suite verifies the supplied implementation; it does not demonstrate independent transfer. Reimplement one follow-up with the reference closed and explain which old invariant no longer holds.

Reference implementation · solution.py

from dataclasses import dataclass

@dataclass(eq=False)
class Node:
    value: object
    next: "Node | None" = None

def _next(node):
    if node is None:
        return None
    if not isinstance(node, Node) or (node.next is not None and not isinstance(node.next, Node)):
        raise ValueError("links must be Node objects or None")
    return node.next

def _validate(head):
    slow = fast = head
    while fast is not None:
        fast = _next(_next(fast))
        slow = _next(slow)
        if fast is not None and slow is fast:
            raise ValueError("chains must be acyclic")
    current, tail, previous_value = head, None, None
    while current is not None:
        if type(current.value) is not int:
            raise ValueError("values must be integers")
        if previous_value is not None and previous_value > current.value:
            raise ValueError("chains must be nondecreasing")
        previous_value = current.value
        tail, current = current, current.next
    return tail

def merge_sorted_lists(first, second):
    first_tail, second_tail = _validate(first), _validate(second)
    if first_tail is not None and first_tail is second_tail:
        raise ValueError("chains must not share nodes")
    dummy = Node(0)
    tail = dummy
    while first is not None and second is not None:
        if first.value <= second.value:
            chosen, first = first, first.next
        else:
            chosen, second = second, second.next
        tail.next = chosen
        tail = chosen
    tail.next = first if first is not None else second
    return dummy.next

Contract and oracle tests · test_solution.py

import itertools
import unittest
from solution import Node, merge_sorted_lists

def chain(values):
    nodes = [Node(value) for value in values]
    for left, right in zip(nodes, nodes[1:]):
        left.next = right
    return nodes

class MergeListTests(unittest.TestCase):
    def test_stable_identity_oracle(self):
        sequences = [values for n in range(4)
                     for values in itertools.combinations_with_replacement(range(3), n)]
        for left in sequences:
            for right in sequences:
                a, b = chain(left), chain(right)
                expected = sorted(a + b, key=lambda node: node.value)
                current = merge_sorted_lists(a[0] if a else None, b[0] if b else None)
                for node in expected:
                    self.assertIs(current, node)
                    current = current.next
                self.assertIsNone(current)

    def test_rejection_precedes_mutation(self):
        tail = Node(3)
        a, b = Node(1, tail), Node(2, tail)
        with self.assertRaises(ValueError):
            merge_sorted_lists(a, b)
        self.assertIs(a.next, tail)
        self.assertIs(b.next, tail)
        for bad in [Node(2, Node(1)), Node(True), Node(1, 42), 42]:
            with self.assertRaises(ValueError):
                merge_sorted_lists(a, bad)
            self.assertIs(a.next, tail)
        cycle = Node(1)
        cycle.next = cycle
        with self.assertRaises(ValueError):
            merge_sorted_lists(a, cycle)
        self.assertIs(cycle.next, cycle)

    def test_deep_chain(self):
        nodes = chain(range(10000))
        self.assertIs(merge_sorted_lists(None, nodes[0]), nodes[0])

if __name__ == "__main__":
    unittest.main()