Linked Lists
Composing three things you already have
The hard-looking problems in this unit are usually three easy ones in a row.
Key idea
The strategy
Some list problems describe a final arrangement that looks nothing like the input, and there is no single loop that produces it. The way in is to ask what sequence of operations you already know would get there.
You can find the middle. You can reverse a list. You can merge two lists. A great many rearrangements are exactly those three, applied in order.
A worked composition
Here is a different rearrangement built the same way: move the second half of a list to the front, keeping both halves in order.
Why it works
The cut is the step people forget
slow.next = None is what actually separates the halves. Without it, the first half still runs all the way through the second, and everything downstream operates on a list you thought you had split.
This produces bugs that look impossible: a reversal that seems to work but leaves a cycle, or a merge that never terminates. If a composed solution loops forever, the missing cut is the first thing to check.
Tip
Starting fast one node ahead
The split above starts fast at head.next rather than at head. That is the trick from the last lesson for landing on the first middle, which is what you need in order to cut before the second half begins.
Same loop, one different starting position, different answer. Worth noticing that the adjustment is made at initialization rather than inside the loop.
Key idea
Interleaving two lists
The last piece some rearrangements need is alternating nodes from two lists rather than merging them by value. The loop takes one from each, saving both next pointers before rewiring, which is the three-reference discipline from the first lesson applied twice at once.
Write it on paper with two three-node lists before coding it. The order of the four assignments is the entire problem, and it is much easier to get right from a drawing than from a guess.
Plan before you type
For the problem below, write down the sequence of operations first, in words. Something like: find the middle, cut, reverse the second part, then interleave.
With that written down it is three functions you have already built and one loop to write. Without it, it is a single enormous function with four pointers and no way to tell which one is wrong.
The pieces
Build the three operations separately so the composition is assembly. reverse reverses a list and returns the new head. split_at_middle returns the two halves, giving the first the extra node when the length is odd, and cuts the link between them. interleave alternates nodes from two lists, starting with the first, and appends anything left over.
Tests
print(to_list(reverse(build([1, 2, 3]))), to_list(reverse(build([])))) a, b = split_at_middle(build([1, 2, 3, 4])) print(to_list(a), to_list(b)) a, b = split_at_middle(build([1, 2, 3, 4, 5])) print(to_list(a), to_list(b)) print(to_list(interleave(build([1, 2]), build([9, 8])))) print(to_list(interleave(build([1]), build([9, 8, 7]))))
Output
Run the tests when you are ready.
Reorder List
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.