Reorder List

medium
Linked ListLinked ListTwo PointersStack

Given the head of a singly linked list, reorder it to follow this pattern: L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Examples

Example 1

  • Input: head = [1,2,3,4]
  • Output: [1,4,2,3]
  • Explanation: The original list 1->2->3->4 is reordered to 1->4->2->3.

Example 2

  • Input: head = [1,2,3,4,5]
  • Output: [1,5,2,4,3]
  • Explanation: The original list 1->2->3->4->5 is reordered to 1->5->2->4->3.

Constraints

  • The number of nodes in the list is in the range [1, 5 * 10^4].
  • 1 <= Node.val <= 1000

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Using a Stack

Intuition

We can use a stack to access nodes from the end of the list easily. First, push all nodes onto a stack. Then, starting from the head, alternately take nodes from the front (via traversal) and from the back (via the stack). We process half the list this way, then terminate the list with a null pointer. The stack gives us O(1) access to the last unprocessed node without needing to reverse anything.

Algorithm

  1. Push all nodes onto a stack.
  2. Calculate the total number of nodes. We need to interleave `(count + 1) / 2` nodes from the front with the rest from the stack.
  3. Starting at `head`, for each of the first half of nodes, pop a node from the stack and insert it after the current node.
  4. Advance the current pointer past the inserted node.
  5. After processing, set the last node's `next` to null to terminate the list.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        stack<ListNode*> stk;
        ListNode* curr = head;
        while (curr) {
            stk.push(curr);
            curr = curr->next;
        }

        int count = stk.size();
        curr = head;
        for (int i = 0; i < count / 2; i++) {
            ListNode* back = stk.top();
            stk.pop();
            back->next = curr->next;
            curr->next = back;
            curr = back->next;
        }
        curr->next = nullptr;
    }
};
Java 21
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        Deque<ListNode> stack = new ArrayDeque<>();
        ListNode curr = head;
        while (curr != null) {
            stack.push(curr);
            curr = curr.next;
        }

        int count = stack.size();
        curr = head;
        for (int i = 0; i < count / 2; i++) {
            ListNode back = stack.pop();
            back.next = curr.next;
            curr.next = back;
            curr = back.next;
        }
        curr.next = null;
    }
}
Python 3.12
def reorderList(head: Optional[ListNode]) -> None:
    if not head or not head.next:
        return

    stack = []
    curr = head
    while curr:
        stack.append(curr)
        curr = curr.next

    count = len(stack)
    curr = head
    for _ in range(count // 2):
        back = stack.pop()
        back.next = curr.next
        curr.next = back
        curr = back.next
    curr.next = None
Go 1.26
func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    var stack []*ListNode
    curr := head
    for curr != nil {
        stack = append(stack, curr)
        curr = curr.Next
    }

    count := len(stack)
    curr = head
    for i := 0; i < count/2; i++ {
        back := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        back.Next = curr.Next
        curr.Next = back
        curr = back.Next
    }
    curr.Next = nil
}
Approach 2

Find Middle, Reverse, Merge

Intuition

The optimal O(1) space approach uses three steps: find the middle of the list, reverse the second half, then merge the two halves by alternating nodes. Finding the middle uses the slow/fast pointer technique. Reversing the second half uses the standard iterative reversal. Finally, we weave the two halves together by alternating pointers. This is the canonical in-place solution.

Algorithm

  1. Use slow and fast pointers to find the middle of the list. After this, `slow` points to the end of the first half.
  2. Reverse the second half of the list starting from `slow.next`.
  3. Disconnect the first half by setting `slow.next = null`.
  4. Merge the two halves by alternating nodes: take one from the first half, then one from the reversed second half.
  5. Continue until both halves are exhausted.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;

        // Find middle
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Reverse second half
        ListNode* prev = nullptr;
        ListNode* curr = slow->next;
        slow->next = nullptr;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        // Merge two halves
        ListNode* first = head;
        ListNode* second = prev;
        while (second) {
            ListNode* tmp1 = first->next;
            ListNode* tmp2 = second->next;
            first->next = second;
            second->next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
};
Java 21
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;

        // Find middle
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Reverse second half
        ListNode prev = null;
        ListNode curr = slow.next;
        slow.next = null;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // Merge two halves
        ListNode first = head;
        ListNode second = prev;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}
Python 3.12
def reorderList(head: Optional[ListNode]) -> None:
    if not head or not head.next:
        return

    # Find middle
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse second half
    prev = None
    curr = slow.next
    slow.next = None
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Merge two halves
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first = tmp1
        second = tmp2
Go 1.26
func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }

    // Find middle
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Reverse second half
    var prev *ListNode
    curr := slow.Next
    slow.Next = nil
    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    // Merge two halves
    first, second := head, prev
    for second != nil {
        tmp1, tmp2 := first.Next, second.Next
        first.Next = second
        second.Next = tmp1
        first = tmp1
        second = tmp2
    }
}

Frequently asked questions

What is the optimal time complexity of Reorder List?

The most efficient approach in this guide ("Find Middle, Reverse, Merge") runs in O(n) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Reorder List use?

Reorder List is a medium-level Linked List problem involving Linked List, Two Pointers, Stack. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Reorder List be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
head=
[1,2,3,4]
Expected Output
[1,4,2,3]