Canonical Deep-Dive: Reorder List

Problem: Reorder List (https://leetcode.com/problems/reorder-list/) The lesson: the three linked-list primitives, stacked in one problem.

This is a guided walk-through, not an answer key. It explains how to think through the problem as a composition of three primitives and shows each one as a relation between pointers, in words and in skeleton pseudocode. It stops short of an assembled, paste-runnable function on purpose, and it deliberately does not hand you a working reversal loop or a working merge loop, because those two are your practice problems this week (Reverse Linked List and Merge Two Sorted Lists). You build them there and reuse them here. The tutor will not confirm your code; LeetCode’s judge will.

Restated: you are given the head of a singly linked list L0 -> L1 -> ... -> L(n-1) -> L(n). Reorder it in place to L0 -> L(n) -> L1 -> L(n-1) -> L2 -> ..., interleaving the front of the list with the back. You may not change the node values; you may only rearrange the nodes themselves by rewiring .next. The function signature is reorder_list(head) -> None: it returns nothing and mutates the list in place.

Why this is the canonical problem

Most linked-list interview questions are a single primitive: find the middle, or reverse a chain, or merge two chains. Reorder List is the rare one that needs all three, in sequence, and it needs them to compose without losing any nodes. That makes it the perfect home for the week’s whole skill. If you can decompose this problem into its three primitives, recognize that you already know each one, and stitch them together with careful pointer bookkeeping, you own the pattern. If you try to solve it in one clever pass, you will tie yourself in knots; the lesson is that the clean solution is three simple steps, not one hard one.

Look at what the target ordering actually is. L0 -> L(n) -> L1 -> L(n-1) -> ... is the first half of the list interleaved with the second half reversed. That observation is the entire decomposition: split the list in the middle, reverse the back half, then zip the two halves together one node at a time.

The brute-force baseline

Before the clean approach, have a baseline so you can see what the three-primitive method buys you. The obvious brute force: to get the last node each time, walk from the current position all the way to the end of the list (O(n) per trip), splice it in behind the current front node, and repeat. That is correct but it walks the tail again on every step.

  • Time: O(n^2). Each of the n placements does an O(n) walk to find the current last node.
  • Space: O(1) if you splice in place, but the quadratic time is the problem.

Alternatively you could copy all the nodes into a list (an actual Python list), then use two indices walking inward from both ends to reorder. That is O(n) time but O(n) extra space for the array of node references. The three-primitive method below beats both: O(n) time and O(1) extra space.

The three primitives, in order

This is the recipe. Walk it in this order, every time.

1. Find the middle (fast and slow pointers). Send a slow pointer one step at a time and a fast pointer two steps at a time from the head. When fast can no longer advance two full steps, slow is at (or just before) the middle. The relation, as a skeleton:

slow = head
fast = head
# advance slow by one and fast by two each iteration,
# while fast can still move two steps;
# when the loop ends, slow is the last node of the first half

The exact loop guard is the detail to pin down by hand, because it decides where slow lands for an even-length versus an odd-length list. Trace your chosen guard on [1,2,3,4] and on [1,2,3,4,5] and confirm slow ends on the last node of the first half (so the first half is the same length as or one longer than the second) before you trust it. This is the same fast/slow idea you will also use in the Linked List Cycle practice problem, pointed at a different question.

2. Reverse the second half (in-place reversal). Cut the list into two halves at the middle (set the first half’s last .next to None), then reverse the second half in place. The in-place reversal is the move you drill in the Reverse Linked List practice problem: walk the chain with a prev pointer trailing behind a curr pointer, and at each node point curr.next back at prev, having first saved the node ahead so you do not lose the rest of the chain. As a relation:

second = slow.next     # head of the second half
slow.next = None        # terminate the first half
# reverse the chain starting at `second`, returning its new head:
#   walk it, pointing each node's .next back at the node behind it,
#   saving the next node BEFORE you flip the pointer (this is the
#   Reverse Linked List primitive you build in practice)
second = reverse(second)

Why save the next node first: the instant you execute curr.next = prev, the original link forward is gone. If you have not stored it, the tail of the list is unreachable. That single ordering rule is the heart of the reversal primitive, and it is why this is a practice problem in its own right.

3. Merge the two halves alternately. You now hold two chains: the first half first (starting at the original head) and the reversed second half second. Weave them together by taking one node from first, then one from second, then one from first, and so on. The merge primitive (taking one node from each chain and relinking) is what you drill in the Merge Two Sorted Lists practice problem; here the twist is that you alternate strictly rather than comparing values, and you use no dummy head because you weave into the existing first-half chain. As a skeleton, the careful part is saving each chain’s next node before you overwrite either pointer:

first  = head                # first half, still in order
second = <the reversed second half>
# until the second half is exhausted:
#   save first.next AND second.next first (you are about to overwrite both)
#   splice the second-half node in just after the current first node
#   then point that spliced node at the saved rest of the first half
#   advance first and second into the two saved positions

Because the second half is the same length as the first half or one shorter (from how step 1 split it), the front list runs out at the right moment and the interleave terminates cleanly. Trace the termination on both an even-length and an odd-length list; getting the loop to stop on the correct node, with the chain ending at None and not looping, is the last detail.

The key insight, in one sentence

The target ordering is the first half interleaved with the reversed second half, so the problem is not one clever pass but three known primitives in sequence: find the middle, reverse the back, merge the two halves alternately. Each primitive is something you already build elsewhere this week; the canonical lesson is the decomposition and the discipline of saving the next pointer before every reassignment so no node is ever lost.

Exact complexity

  • Time: O(n). Finding the middle is one pass (the fast pointer covers the list once). Reversing the second half is one pass over half the list. Merging is one pass over the whole list. Three linear passes is still O(n); there is no nested walk and no sort.
  • Space: O(1). Every step rearranges the existing nodes by reassigning .next; you allocate only a fixed handful of pointer variables (slow, fast, prev, curr, the saved next nodes). No array of nodes, no recursion stack, no second list.

This O(n) time and O(1) space is exactly why the three-primitive method is the answer and the brute-force baselines are not: the quadratic version is too slow, and the copy-into-an-array version pays O(n) memory you do not need.

Your work this week

  1. Implement Reorder List yourself, in your own work repo (for example reorder-list.py), as the three primitives in sequence: find the middle, reverse the second half, merge alternately. Build the reversal and the merge from the practice problems; do not look for a one-pass trick. Reorder is in place, so your function returns None and rewires the nodes it was given.
  2. Test the edge cases yourself before submitting: the empty list (head is None), a single node (already reordered, nothing to do), a two-node list (already reordered), and then a four-node and a five-node list to check that the even and odd split and the merge termination both behave. The provided examples are [1,2,3,4] becoming [1,4,2,3] and [1,2,3,4,5] becoming [1,5,2,4,3].
  3. Trace your pointer moves on paper for [1,2,3,4] once, node by node, through all three steps. Confirm that at no point have you orphaned a node, and that the final chain ends at None (not in a loop). This hand-trace is the cheapest way to find the “lost the tail” bug.
  4. Commit with a five-question debrief in the message. In answer 3, state the exact complexity above (three linear passes, O(n) time, O(1) space) and why the array-copy alternative is worse on space.

When you can explain, from memory and with no AI open, the three primitives in order, why the target ordering is “first half interleaved with reversed second half”, and why you must save the next pointer before every reassignment, you own this problem. That explanation is exactly what an interviewer will ask for, and the decomposition is the template you will reuse on every multi-step linked-list problem.