Reorder List

Interview Problem Interview Medium Fast and Slow Pointers Linked List

Checking your account…

Loading the interactive Interview workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Interview workspace

Problem

Implement Solution.reorderList(head). Reorder nodes L0→L1→…→Ln into L0→Ln→L1→Ln-1→… without changing values. Return head after the in-place reorder so the Judge can inspect it.

Starter code

class Solution:
    def reorderList(self, head):
        pass

Test cases

even

{
  "args": [
    {
      "$type": "linked-list",
      "values": [
        1,
        2,
        3,
        4
      ]
    }
  ]
}

Expected: {"$type":"linked-list","values":[1,4,2,3]}

Wizard outline

Step 1: Initialize Solution.reorderList
Replace the empty starter with the first real state owned by Solution.reorderList. A small, named state is easier to verify than a complete algorithm. Establish it before adding the branch or loop that changes it.
Step 2: Pass the Short case
Complete the readable core algorithm for one representative Interview case. A short list has nothing to reorder, so returning early keeps later midpoint logic safe and focused.
Step 3: Harden the Even boundary
Repair the reviewed boundary and pass the complete submission contract. The split partitions all nodes, reversal exposes them from Ln backward, and weaving preserves first-half order while inserting second-half nodes in reverse order, exactly producing the required sequence without duplication.

Footguns and prerequisites

Disconnect the first half before reversing or weaving can create a cycle.
linked lists

Reviewed references

LeetCode 143 — Reorder List

Practice prerequisites

Relink Nodes Safely(opens in a new tab)
Relink Nodes Safely isolates every untouched node keeps its original next link, and at most one predecessor changes to the removed node’s former successor. That focused state discipline is required when implementing reorder list as a complete Interview Problem.
Trace Fast and Slow Pointers(opens in a new tab)
Trace Fast and Slow Pointers isolates after each loop, slow has advanced one link for every two links attempted by fast. That focused state discipline is required when implementing reorder list as a complete Interview Problem.

Recommended approach and implementation

Use slow/fast to end the first half, reverse the detached second half, then alternate one node from each chain.

Why it works: The split partitions all nodes, reversal exposes them from Ln backward, and weaving preserves first-half order while inserting second-half nodes in reverse order, exactly producing the required sequence without duplication.

class Solution:
    def reorderList(self, head):
        """
        Checkpoint 1: initialize the state owned by this Interview contract.
        Checkpoint 2: assemble the primary transition without hiding the boundary.
        """
        if not head or not head.next:
            return head
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        second = slow.next
        slow.next = None
        previous = None
        while second:
            following = second.next
            second.next = previous
            previous = second
            second = following
        first, second = head, previous
        while second:
            next_first, next_second = first.next, second.next
            first.next = second
            second.next = next_first
            first, second = next_first, next_second
        return head

Similar exercises

Odd Even Linked List(opens in a new tab)