LeetCode 143 · Linked List

Reorder List, explained with a picture

Zipping the front of a train with its back.

MediumLinked List
▶ Watch it step by step

The problem

Reorder a linked list L0 → L1 → … → Ln into L0 → Ln → L1 → Ln−1 → L2 → …, changing links, not values.

Input:  1 → 2 → 3 → 4 → 5
Output: 1 → 5 → 2 → 4 → 3

Picture it

Picture the train being zipped like a jacket. Step 1: a tortoise (1 step) and a hare (2 steps) find the middle coach. Step 2: reverse the back half, so it now runs from the last coach inward. Step 3: zip the two halves together, alternating a coach from the front half and a coach from the reversed back half.

How to recognise it

  • The output alternates between the front and the back of a singly linked list: first, last, second, second-to-last, and so on.
  • You can only walk forwards, yet you need the back half in reverse order. Reversing that half turns "walk backwards" into "walk forwards".
  • You must relink nodes, not swap values, and the expected solution uses O(1) extra space.
  • Up to 5 × 10^4 nodes, so walking to the tail again for every node is too slow.
  • The task splits into three moves you may already know: find the middle (fast and slow pointers), reverse a list, and merge two lists.

Start with brute force

Take the nodes one at a time from the front. For each, walk to the end, unhook the last node and insert it right after the current one.

def reorder_brute(head):
    curr = head
    while curr and curr.next and curr.next.next:
        before_last = curr
        while before_last.next.next:
            before_last = before_last.next
        last = before_last.next
        before_last.next = None
        last.next = curr.next
        curr.next = last
        curr = last.next

It is correct and uses O(1) extra space, but each walk to the end costs up to n steps, so time is O(n²). For 5 × 10^4 nodes that is roughly 6 × 10^8 steps. Storing all nodes in an array fixes the time (two indices meet in the middle) but costs O(n) space.

From brute force to the idea

  1. Find the waste. The brute force walks to the tail again and again only because it cannot move backwards. The order it needs from the back half is simply that half reversed.
  2. Find the middle. slow moves one step and fast two. The loop while fast.next and fast.next.next stops with slow at the last node of the front half; for odd lengths the front half gets the extra node (1 2 3 | 4 5).
  3. Cut and reverse. Set slow.next = None so the halves are separate lists, then reverse the back half with the usual three-pointer loop (prev, curr and the next node, here in one tuple assignment). prev ends as the old tail.
  4. Zip. Take a from the front half and b from the reversed back half. Link a → b, then b → the next front node, and move both on. Python evaluates the right side of a.next, a = b, a.next before assigning, so the old a.next is saved for free.
  5. Stop when the back half runs out. The back half is never longer than the front, so while b is enough. The front half's last node already ends in None.

This is the key idea: middle, reverse, merge, each in O(n) time and O(1) space.

The key idea

Find the middle, reverse the second half, merge alternately. O(n) time, O(1) space.

Python solution

def reorder_list(head):
    slow = fast = head
    while fast.next and fast.next.next:     # 1. find the middle
        slow, fast = slow.next, fast.next.next
    prev, curr = None, slow.next          # 2. reverse the back half
    slow.next = None
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    a, b = head, prev                     # 3. zip the halves
    while b:
        a.next, a = b, a.next
        b.next, b = a, b.next

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(n²): a walk to the tail for every pair of nodesO(1): a few references
Middle, reverse, zip (shown code)O(n): three passes, each over at most n nodesO(1): a fixed number of references, nodes are relinked

Edge cases

  • One node: the middle loop does not run, the back half is empty, and the list is unchanged.
  • Two nodes (1 → 2): slow stays at 1, the back half is just 2, and the list stays 1 → 2.
  • Even length (1 → 2 → 3 → 4): becomes 1 → 4 → 2 → 3.
  • Odd length (1 → 2 → 3 → 4 → 5): becomes 1 → 5 → 2 → 4 → 3, and node 3 ends with None.
  • Empty list: LeetCode guarantees at least one node. The shown code reads fast.next straight away, so head = None raises AttributeError; add if not head: return to be safe.
  • Return value: the function changes the list in place and returns None, as LeetCode expects.

Common mistakes

  • Forgetting slow.next = None. The front half still runs into the back half, and the zip creates a cycle.
  • Zipping while a instead of while b. The front half can be one node longer, so for odd lengths (and a single node) the last step runs b.next on None and raises AttributeError.
  • Writing the zip as separate statements (a.next = b then a = a.next), which moves a onto b instead of the next front node.
  • Swapping values instead of relinking nodes.
Your turn: palindrome list

Decide whether a singly linked list reads the same forwards and backwards (1 → 2 → 2 → 1 is true, 1 → 2 is false), in O(n) time and O(1) extra space. Describe your approach, then write it if you like.

Compare with our answer

Use the same first two moves. Find the middle, reverse the back half, then walk the front and the reversed back side by side, comparing values instead of zipping.

def is_palindrome(head):
    slow = fast = head
    while fast and fast.next:          # slow ends at the middle
        slow, fast = slow.next, fast.next.next
    prev = None
    while slow:                        # reverse from the middle on
        slow.next, prev, slow = prev, slow, slow.next
    a, b = head, prev
    while b:
        if a.val != b.val:
            return False
        a, b = a.next, b.next
    return True

Time O(n), space O(1). It changes the list; reverse the back half again if the caller still needs it.

A strong answer mentions: the fast/slow middle, comparing only until the reversed half runs out, why the odd middle node needs no check, and that the input is modified.

Check what stuck

1. For a list of even length, the "twin" of node i is node n − 1 − i. Find the largest sum of twins in O(1) extra space. Which approach fits best?

2. Why does the shown code use O(1) extra space, while the array version uses O(n)?

3. A learner deletes slow.next = None. What happens for 1 → 2 → 3 → 4?

Score 60% or more and the lesson is marked complete.