Linked Lists
Merging many by merging two, repeatedly
Pair them up and merge in rounds. The complexity difference against the obvious approach is the lesson.
The obvious approach, and its cost
You can already merge two sorted lists. To merge k of them, the obvious move is to merge the first two, then merge that result with the third, and so on.
That is correct and slow. The accumulator grows by n nodes each round and is walked in full every time, so the total work is n, then 2n, then 3n, and so on up to k rounds. That sums to about n times k squared over two, which is O(n k squared).
Why it works
Merge in rounds instead
Pair the lists up and merge each pair. That halves how many lists remain. Repeat until one is left.
Every round touches every node exactly once, so a round costs O(n k). The number of rounds is how many times you can halve k, which is log k. Total O(n k log k), and the difference against the accumulating version grows fast with k.
Only the count matters for that argument, so watch it rather than the contents. Five lists take three rounds, not five.
Edge cases
The odd one out
When the count is odd, the last list has no partner. Carrying it unchanged into the next round is correct and is the only thing to get right in the pairing loop.
Stepping the loop by two and checking that the partner index is in range handles it in one condition. Forgetting the check raises IndexError on any odd count, which is half of all inputs.
Tip
The structure does not care what it is merging
The round loop above never looks inside a list. It pairs, merges, and repeats, and the only thing specific to this problem is which merge it calls. For linked lists that is the dummy-head merge you already wrote, returning a head rather than an array.
That independence is worth noticing, because the same shape appears in merge sort and in any other divide-and-conquer combine. Getting the round loop right once means getting it right everywhere.
Key idea
The heap alternative, for later
There is a second solution that keeps one candidate from each list in a structure that always hands back the smallest, pulling nodes one at a time. That is O(n k log k) as well, with a different constant and a different shape.
It needs a heap, which arrives in Unit 9, and this problem returns there as a review so you can build it the other way. Two correct solutions with the same complexity and completely different structure is a good thing to have met.
Cost of the accumulating approach
Suppose you merge k sorted lists by repeatedly merging the running result with the next list. With k lists of n nodes each, what is the total time? Give space as the extra space beyond the output.
Time
Space
Merge K Sorted Lists
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.