Problem. Given the heads of two sorted linked lists a and b, merge them into one sorted list made of the
same nodes, and return its head.
a = 1 → 2 → 4, b = 1 → 3 → 4 → 1 → 1 → 2 → 3 → 4 → 4
a = None, b = 0 → 0
This is the merge step of merge sort, and the core of every "combine sorted streams" problem: compare the two fronts, take the smaller, repeat.
ML context. Sorted streams are everywhere in data systems: per-worker event logs sorted by timestamp, per-shard search results sorted by score, posting lists of document ids in an inverted index. Merging them without re-sorting is how a training data pipeline interleaves shards in time order, and how a retrieval system combines candidates from several retrievers (Changes C and D).