Where it runs
1. The problem
Two services each send you a feed of events. Each feed is already in order by event time. The reader needs one combined feed, also in order. So the input is two sorted chains, and the output has to be one sorted chain.
The most direct way: put both into an array, join them, and sort. That works, but it doesn't use the fact that each input is already sorted. You pay for a full sort that isn't needed here, and for the memory of a new array too.
Both chains are already in order, so you can weave them together while looking only at the two first nodes. Take the smaller one, move to the next node in the chain you took it from, and repeat. One pass, with no new sort and no new list.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedmergeTwoLists(1 → 4 → 5, 2 → 4 → 6 → 8)Merge two sorted lists into one sorted list. The result starts at a dummy node, and tail points at it.
Recognise it
Say these words and it is this pattern
- merge two sorted linked lists
- merge k sorted lists
- reorder a list (interleave front and back halves)
- rearrange nodes without copying values into an array
- dummy head / sentinel node
Looks similar, isn't
- Linked list reversal
Reversal flips the links inside one list. Merging re-links nodes across two lists.
- Binary heap / priority queue
With k lists a heap picks the smallest front in log k. With two lists one comparison is enough.
- Fast sort (merge / quick)
The merge step of merge sort is this exact loop. Here the lists arrive already sorted.
- Fast & slow pointers
Reordering starts by finding the middle, which is that pattern. The weave afterwards is this one.
n plus m nodes gives O(n + m) time and O(1) space. Merging k lists with a heap costs O(N log k).
On LeetCode
Problems that merge sorted linked lists, sort a linked list, or reorder one by splitting and weaving its halves. A dummy head and one comparison per node do the merge.
This is the lesson task, dummy head included.
Find the middle (lesson 47), reverse the back half (lesson 46), then weave the halves one node at a time.
Merge sort on nodes, splitting at the middle and merging with this lesson's function.
Merge the lists in pairs, then pairs of the results, until one list is left.