Generated by Codex with GPT 5.6 Sol XHigh

Quick facts

• Difficulty: MEDIUM
• Problem: Reorder List
• Topics: Linked List, Two Pointers, Stack, Recursion

Problem gist

The input is a singly linked list in its ordinary front-to-back order:

L0 → L1 → L2 → ... → Ln

It must be rearranged by alternating nodes from the front and back:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...

For example, 1 → 2 → 3 → 4 → 5 becomes 1 → 5 → 2 → 4 → 3. The existing nodes must be relinked in place; copying values into a new order does not meet the problem’s requirement.

A stack makes the back of the list easy to reach, but it stores every node and therefore costs O(n) extra space. The optimal solution takes O(n) time and O(1) auxiliary space by turning the reorder into three familiar linked-list operations.

Deriving the optimal solution

The desired output is a weave of the list’s first half in forward order and its second half in reverse order. That observation gives a direct plan.

First, find the last node of the first half with slow and fast pointers. The slow pointer advances one node while the fast pointer advances two. When the fast pointer reaches the end, the slow pointer is at the split point. For an odd-length list, the first half deliberately receives the extra middle node.

Second, detach and reverse the second half. Reversal changes the nodes that originally appeared from the middle to the tail into the exact order needed for weaving: tail first, then the node before it, and so on.

Finally, merge the two halves by alternating one node from each. Before changing any next link, save the next nodes from both halves. Then connect one node from the first half to one from the reversed half and continue. The reversed half is never longer than the first, so every one of its nodes can be inserted safely.

For 1 → 2 → 3 → 4 → 5, the phases are:

1. Split into 1 → 2 → 3 and 4 → 5.
2. Reverse the second half into 5 → 4.
3. Weave the halves into 1 → 5 → 2 → 4 → 3.

Splitting before the reverse is important in production-quality code. It makes the two halves independent and prevents a stale link from accidentally creating a cycle while nodes are rewired.

Why the algorithm is optimal

Finding the midpoint, reversing the second half, and weaving the halves each touch at most n nodes. Their work is sequential rather than nested, so the total running time is O(n). The algorithm stores only a fixed number of node references, giving O(1) auxiliary space.

Any correct algorithm needs O(n) time in the worst case because the original tail must become the second node, and a singly linked list offers no way to discover that tail without following the links to it. The three-phase method reaches this lower bound while also using the minimum asymptotic extra space.

Python solution

from __future__ import annotations


# LeetCode provides this class:
# class ListNode:
#     def __init__(self, value: int = 0, next_node: ListNode | None = None):
#         self.val = value
#         self.next = next_node


class LinkedListReorderer:
    """Reorder a singly linked list in place using constant extra space."""

    @classmethod
    def reorder(cls, head: ListNode | None) -> None:
        """Change head's links to alternate nodes from the front and back."""
        if head is None or head.next is None:
            return

        first_half_tail = cls._find_first_half_tail(head)

        # Detach the halves before reversal so no obsolete link can form a
        # cycle while the nodes are being rewired.
        second_half_head = first_half_tail.next
        first_half_tail.next = None
        reversed_second_half = cls._reverse(second_half_head)

        cls._weave(head, reversed_second_half)

    @staticmethod
    def _find_first_half_tail(head: ListNode) -> ListNode:
        """Return the first half's tail; it includes the middle odd node."""
        slow_pointer = head
        fast_pointer = head

        while fast_pointer.next is not None and fast_pointer.next.next is not None:
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

        return slow_pointer

    @staticmethod
    def _reverse(head: ListNode | None) -> ListNode | None:
        """Reverse a list and return its new head."""
        previous_node = None
        current_node = head

        while current_node is not None:
            next_node = current_node.next
            current_node.next = previous_node
            previous_node = current_node
            current_node = next_node

        return previous_node

    @staticmethod
    def _weave(
        first_half_head: ListNode,
        second_half_head: ListNode | None,
    ) -> None:
        """Insert each second-half node after the next first-half node."""
        first_node = first_half_head
        second_node = second_half_head

        while second_node is not None:
            next_first_node = first_node.next
            next_second_node = second_node.next

            first_node.next = second_node
            second_node.next = next_first_node

            # The first half is at least as long as the second half.
            first_node = next_first_node
            second_node = next_second_node


class Solution:
    """LeetCode-compatible entry point."""

    def reorderList(self, head: ListNode | None) -> None:
        LinkedListReorderer.reorder(head)

Interview follow-ups

How would the solution change if extra memory were allowed?

Push every node onto a stack, then walk forward from the head while repeatedly taking a node from the stack and inserting it after the current front node. Stop after half the nodes have been placed and terminate the final node with None so that old links do not create a cycle.

The stack exposes the nodes from tail to head, so it produces exactly the required back-half order. This version is still O(n) time, and many candidates find it easier to derive, but its O(n) auxiliary space is worse than the in-place solution’s O(1).

Can the list be reordered recursively?

A recursive solution can descend to the tail and, as calls return, splice each back node after a front pointer that advances from the head. It must stop carefully when the two directions meet or cross, and it must set the final next link to None.

The recursion works because the call stack reveals nodes in reverse order, much like an explicit stack. It takes O(n) time but also O(n) call-stack space, and a long list can exceed Python’s recursion limit. The iterative three-phase solution is safer when constant auxiliary space or production robustness matters.

What if the original list must remain unchanged?

An in-place reorder is incompatible with preserving all original links. Instead, read the node values into an array and build a new list by taking indices from the left and right ends alternately. If node identity rather than values must be preserved, the API needs a different representation, such as returning an ordered array of references without changing their links.

Building a new list takes O(n) time and O(n) extra space. That cost is necessary because the result and the original must coexist as independently linked structures.

How should the implementation handle an input that may contain a cycle?

The LeetCode contract supplies an acyclic list, but a more defensive API can first run Floyd’s slow-and-fast cycle detection. If the pointers meet, reject the input or report a validation error before attempting to find the midpoint. Otherwise, proceed with the normal reorder.

The validation pass is O(n) time and O(1) space, so it does not change the asymptotic bounds. It does add another traversal, but it prevents midpoint and reversal loops from running forever on malformed input.

Can the reorder be completed in a single traversal?

Not for an ordinary singly linked list with O(1) extra space. The second output node is the original tail, but the tail is unknown until traversal reaches it. Earlier links therefore cannot be finalized while the list is first being explored unless the algorithm stores enough nodes to revisit them conveniently.

The optimal in-place method uses several linear passes, but big-O time counts their sum: O(n) + O(n) + O(n) is still O(n). An array-backed sequence or a doubly linked list changes the access model and can make front-and-back selection more direct, but it does not improve the O(n) total work needed to reorder every element.