Tech Blogs LLD SDE Playbook DSA

Reorder List

Medium Blind 75 Top 250
Associated Patterns
Linked List
Interviewed At (Company Tags)
AmazonGoogleMetaMicrosoft
External Reference View on LeetCode

Problem Description

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

You may not modify node values. Only nodes themselves may be changed.

Examples

Example 1:

Input: head = [1,2,3,4] Output: [1,4,2,3]

Example 2:

Input: head = [1,2,3,4,5] Output: [1,5,2,4,3]

Constraints

  • The number of nodes in the list is in the range [1, 5 * 10⁴].
  • 1 ≤ Node.val ≤ 1000

The Pattern Is Interleaving the First Half with the Reversed Second Half

The output is always: first node, last node, second node, second-to-last, etc. That’s the first half interleaved with a reversed second half. If you split the list at the midpoint, reverse the second half, and merge the two halves by alternating nodes, you get the output directly.

Three steps, each O(n), each using O(1) space.

Solution 1: Collect Into Array Then Rebuild

Load all nodes into an array, then use two-pointer index arithmetic to reconstruct the ordering.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public void reorderList(ListNode head) {
        List<ListNode> nodes = new ArrayList<>();
        ListNode curr = head;
        while (curr != null) { nodes.add(curr); curr = curr.next; }

        int left = 0, right = nodes.size() - 1;
        while (left < right) {
            nodes.get(left).next = nodes.get(right);
            left++;
            if (left == right) break;
            nodes.get(right).next = nodes.get(left);
            right--;
        }
        nodes.get(left).next = null;  // terminate the list
    }
}
class Solution:
    def reorderList(self, head: ListNode) -> None:
        nodes = []
        curr = head
        while curr:
            nodes.append(curr)
            curr = curr.next

        left, right = 0, len(nodes) - 1
        while left < right:
            nodes[left].next = nodes[right]
            left += 1
            if left == right:
                break
            nodes[right].next = nodes[left]
            right -= 1
        nodes[left].next = None  # terminate the list
#include <vector>

class Solution {
public:
    void reorderList(ListNode* head) {
        std::vector<ListNode*> nodes;
        ListNode* curr = head;
        while (curr) { nodes.push_back(curr); curr = curr->next; }

        int left = 0, right = nodes.size() - 1;
        while (left < right) {
            nodes[left]->next = nodes[right];
            left++;
            if (left == right) break;
            nodes[right]->next = nodes[left];
            right--;
        }
        nodes[left]->next = nullptr;  // terminate the list
    }
};

Complexity Analysis:

  • Time Complexity: O(n). One pass to collect, one pass to reorder.
  • Space Complexity: O(n). Array storing all node references.

Where it breaks: uses O(n) extra space. The in-place approach below does it in O(1).

Solution 2: Find Middle, Reverse Second Half, Merge

Three steps in-place.

class Solution {
    public void reorderList(ListNode head) {
        // Step 1: find the middle
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: reverse the second half starting after the midpoint
        ListNode second = slow.next;
        slow.next = null;  // cut the list in two
        ListNode prev = null;
        while (second != null) {
            ListNode next = second.next;
            second.next = prev;
            prev = second;
            second = next;
        }

        // Step 3: merge by alternating nodes from each half
        ListNode first = head, secondHead = prev;
        while (secondHead != null) {
            ListNode tmp1 = first.next, tmp2 = secondHead.next;
            first.next = secondHead;
            secondHead.next = tmp1;
            first = tmp1;
            secondHead = tmp2;
        }
    }
}
class Solution:
    def reorderList(self, head: ListNode) -> None:
        # Step 1: find the middle
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # Step 2: reverse the second half starting after the midpoint
        second = slow.next
        slow.next = None  # cut the list in two
        prev = None
        while second:
            tmp = second.next
            second.next = prev
            prev = second
            second = tmp

        # Step 3: merge by alternating nodes from each half
        first, second = head, prev
        while second:
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first, second = tmp1, tmp2
class Solution {
public:
    void reorderList(ListNode* head) {
        // Step 1: find the middle
        ListNode* slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }

        // Step 2: reverse the second half starting after the midpoint
        ListNode* second = slow->next;
        slow->next = nullptr;  // cut the list in two
        ListNode* prev = nullptr;
        while (second) {
            ListNode* next = second->next;
            second->next = prev;
            prev = second;
            second = next;
        }

        // Step 3: merge by alternating nodes from each half
        ListNode* first = head;
        second = prev;
        while (second) {
            ListNode* tmp1 = first->next, *tmp2 = second->next;
            first->next = second;
            second->next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
};

Complexity Analysis:

  • Time Complexity: O(n). Three linear passes: find middle, reverse, merge.
  • Space Complexity: O(1). All pointer manipulation in-place.

Where it breaks: if you forget to cut the list (slow.next = null) between steps 2 and 3, the reverse step creates a cycle in the original list and the merge step runs infinitely.

Common Mistakes

  • Not cutting the list before reversing. Without slow.next = null, the second half’s tail still points somewhere in the first half, causing the reverse to create a cycle.
  • Using fast.next.next without checking fast.next != null first. This null pointer dereference crashes on even-length lists where fast.next is null before fast.next.next can be accessed.
  • Confusing the merge step’s termination. The merge loop runs while secondHead != null, not while first != null. The first half is always at least as long as the second half (or equal). Looping on second is safe.

Frequently Asked Questions

Why use slow/fast pointers to find the middle? It’s a single pass that finds the midpoint without knowing the list length. The alternative (count nodes, then walk to n/2) requires two passes and doesn’t save any time.

What defines “middle” for an even-length list? Slow/fast gives you the first of the two middle nodes for even-length lists. For [1,2,3,4], slow lands on node 2. The second half starts at node 3 (slow.next). This produces [1,4,2,3], which matches the expected output.

Is there a simpler recursive solution? Yes, but it requires O(n) call stack space and is significantly harder to get right. The three-step iterative approach is what interviewers expect here.

← All Problems