Lesson 24 — Composing Linked-List Primitives

~25 minutes · linked-list composition · Python · Day 26

Tonight you solve Reorder List. Interviewers like this one because it is not one new trick. It is a test of whether you can compose three small linked-list moves without losing a pointer: find the middle, reverse the back half, then weave the two halves together.

The invariant

Hard problems are compositions: find the middle, reverse the second half, then merge the two halves alternately.

A linked list is a chain of nodes where each node points to the next one (Wikipedia: linked list). Reorder List asks for L0 → Ln → L1 → Ln-1..., and the statement says not to change node values, only the links between nodes (LeetCode: Reorder List).

Reorder List: the slow way first

The brute-force idea is to keep pulling the current tail to the front side. Put the last node after the first node, then put the new last node after the second node, and so on. It uses only pointers, but each pull has to scan from the current front to find the tail and the node before it.

front = head
while front and front.next:
    prev, tail = front, front.next
    while tail.next:                 # rescan to find current tail
        prev, tail = tail, tail.next
    # detach tail, insert it after front, then advance front

That repeated tail scan is the problem. On a long list, you do a long scan, then a slightly shorter scan, then another one. The total work becomes O(n²). The better approach spends one pass to locate the middle, one pass to reverse the second half, and one pass to weave.

Reorder List: the compound way

Use fast/slow pointers to stop near the middle. Cut the list there. Reverse the second half with the standard prev, curr, next move. Then merge by alternating one node from the first half and one node from the reversed second half.

The list becomes manageable when you split once, reverse the back half once, then weave one node from each side.

def reorderList(head):
    slow = fast = head                  # 1) find the middle
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    second, slow.next = slow.next, None # split after the middle
    prev = None
    while second:                       # 2) reverse second half
        nxt = second.next; second.next = prev; prev, second = second, nxt
    first, second = head, prev
    while second:                       # 3) weave alternately
        n1, n2 = first.next, second.next
        first.next = second; second.next = n1; first, second = n1, n2

The merge loop saves n1 and n2 before rewiring. That is the pointer-safety rule here: save the next nodes before changing any .next links that could make the rest of the list unreachable.

Saving n1 and n2 before rewiring preserves the only routes to nodes that have not been woven yet.

Transfer: same composition, new finish line

Maximum Twin Sum of a Linked List: pair the first node with the last, the second with the second-last, and return the largest pair sum. Before opening the reveal, predict the reusable pieces. Which two primitives prepare the list, and what replaces the alternating merge?

What the trade buys you

The time win comes from refusing to search for the tail over and over. Every node is visited a constant number of times, and the only extra storage is a handful of pointers.

Practice — answer before you scroll past

second = slow.next
# slow.next is still connected

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Reorder List — predict the O(n²) tail-scan version first, then attempt the three-primitive version from the invariant.

For the encode step, write the three moves in one sentence and name the pointer that must be saved before each rewire.