Skip to main content
CodePeetCodePeet
CodePeet 250

Reorder List

MEDIUMProblemSolveExternal Links

Description

You are given the head of a singly linked list. The list can be represented as:

L0 → L1 → … → Ln-1 → Ln

Reorder the list so that it follows this pattern:

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

In other words, interleave nodes from the beginning and the end of the list. The first node stays first, the last node comes second, the second node comes third, the second-to-last comes fourth, and so on.

You may not modify the values in the list's nodes. Only the nodes themselves (their next pointers) may be changed. The reordering must be done in-place.

Examples

Example 1

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

Output: [1, 4, 2, 3]

Explanation: The original list is 1→2→3→4. Following the pattern L0→L3→L1→L2, we get 1→4→2→3. The first node (1) stays, the last node (4) is placed after it, then the second node (2), then the second-to-last node (3).

Example 2

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

Output: [1, 5, 2, 4, 3]

Explanation: The original list is 1→2→3→4→5. Following the pattern L0→L4→L1→L3→L2, we get 1→5→2→4→3. The middle node (3) ends up at the tail since it has no partner to interleave with.

Example 3

Input: head = [1]

Output: [1]

Explanation: A single-node list is already in the correct order. No reordering needed.

Constraints

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

Editorial

Brute Force

Intuition

The challenge with a singly linked list is that we can only traverse it forward — there is no way to jump to the last node or walk backward. But the reorder pattern demands that we alternate between the front and the back of the list.

The simplest way to overcome this limitation is to store all nodes in an array. Once the nodes are in an array, we have random access — we can reach the first node and the last node equally fast using indices. Then we use two pointers: one starting from the beginning (left) and one from the end (right), and we stitch the nodes together in alternating order.

Think of it like arranging a deck of cards. The linked list is a stack of cards you can only see from the top. You lay them all out on a table (the array), then pick from the left end and right end alternately to build the reordered sequence.

Step-by-Step Explanation

Let's trace with head = [1, 2, 3, 4, 5]:

Step 1: Traverse the linked list and store all nodes in an array.

  • nodes = [Node(1), Node(2), Node(3), Node(4), Node(5)]

Step 2: Initialize two pointers: left = 0, right = 4.

Step 3: Pick from left: Node(1). Pick from right: Node(5).

  • Link: Node(1).next = Node(5)
  • left = 1, right = 3

Step 4: Pick from left: Node(2). Pick from right: Node(4).

  • Link: Node(5).next = Node(2), Node(2).next = Node(4)
  • left = 2, right = 2

Step 5: left == right, so Node(3) is the middle. Place it at the end.

  • Link: Node(4).next = Node(3)
  • Node(3).next = null (terminate the list)

Step 6: Final list: 1→5→2→4→3

Brute Force — Array + Two Pointers Interleaving — Watch how we store list nodes in an array, then use left/right pointers to pick alternately from front and back, building the reordered list.

Algorithm

  1. Traverse the linked list, storing each node in an array nodes
  2. Initialize left = 0, right = nodes.length - 1
  3. While left < right:
    • Link nodes[left].next = nodes[right]
    • Increment left
    • If left == right, break (odd-length list, middle node placed)
    • Link nodes[right].next = nodes[left]
    • Decrement right
  4. Set nodes[left].next = null to terminate the list

Code

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        
        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;
    }
};
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return
        
        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
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        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;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the list once to build the array (O(n)), then use two pointers to relink the nodes in a single pass (O(n)). Total: O(n).

Space Complexity: O(n)

We store all n nodes in an array. This is the main drawback — we use extra space proportional to the size of the list.

Why This Approach Is Not Efficient

The brute force uses O(n) extra space to store all nodes in an array. With up to 5 × 10^4 nodes, this is a significant memory overhead.

The fundamental issue is that we convert the linked list into an array just to gain the ability to access the last node. But do we really need to store all nodes?

The reorder pattern interleaves nodes from the front half and the back half. If we could:

  1. Split the list into two halves
  2. Reverse the second half (so we can traverse it forward instead of needing backward access)
  3. Merge the two halves by alternating nodes

...then we could achieve the same result using only O(1) extra space. Each of these three sub-operations can be performed in-place on a linked list, which leads us to the optimal approach.

Optimal Approach - Find Middle + Reverse + Merge

Intuition

This approach combines three classic linked list techniques into one elegant solution:

Step A — Find the Middle: Use the slow-fast pointer technique. A slow pointer moves one node at a time, while a fast pointer moves two nodes at a time. When fast reaches the end, slow is at the middle. This splits the list into a first half and a second half.

Step B — Reverse the Second Half: Reverse the second half of the list in place. After reversal, the last node of the original list becomes the first node of the reversed half. Now both halves can be traversed forward.

Step C — Merge Alternately: Take one node from the first half, then one from the reversed second half, alternating until all nodes are connected.

Imagine a line of people standing in order 1 through 5. You split them at the middle: group A is [1, 2, 3] and group B is [4, 5]. You reverse group B to get [5, 4]. Then you interleave: 1, 5, 2, 4, 3. That's the reordered list!

Each of the three sub-steps runs in O(n) time and O(1) space, giving an overall O(n) time, O(1) space solution.

Step-by-Step Explanation

Let's trace with head = [1, 2, 3, 4, 5]:

Phase A: Find the Middle

Step 1: Initialize slow = Node(1), fast = Node(1).

Step 2: Move slow one step: slow = Node(2). Move fast two steps: fast = Node(3).

Step 3: Move slow one step: slow = Node(3). Move fast two steps: fast = Node(5).

Step 4: fast.next is null, so stop. slow = Node(3) is the middle. Split: first half = [1, 2, 3], second half starts at Node(4). Set Node(3).next = null.

Phase B: Reverse the Second Half

Step 5: Second half is 4→5. Reverse it to 5→4.

  • prev = null, curr = Node(4)
  • next = Node(5), Node(4).next = null, prev = Node(4), curr = Node(5)
  • next = null, Node(5).next = Node(4), prev = Node(5), curr = null
  • Reversed second half head = Node(5). Chain: 5→4.

Phase C: Merge Alternately

Step 6: first = Node(1), second = Node(5).

  • Save: first.next = Node(2), second.next = Node(4)
  • Link: Node(1).next = Node(5), Node(5).next = Node(2)
  • Advance: first = Node(2), second = Node(4)

Step 7: first = Node(2), second = Node(4).

  • Save: first.next = Node(3), second.next = null
  • Link: Node(2).next = Node(4), Node(4).next = Node(3)
  • Advance: first = Node(3), second = null

Step 8: second is null → merging complete.

Result: 1→5→2→4→3

Optimal — Find Middle, Reverse, Merge on [1,2,3,4,5] — Watch the three-phase algorithm: slow/fast pointers find the middle, the second half is reversed in place, then both halves are merged by alternating nodes.

Algorithm

  1. Find the middle using slow/fast pointers:
    • slow moves 1 step, fast moves 2 steps
    • When fast reaches the end, slow is at the middle
  2. Split the list into two halves at the middle:
    • second_half = slow.next
    • slow.next = null
  3. Reverse the second half in place:
    • Use three pointers (prev, curr, next) to reverse all links
  4. Merge the two halves alternately:
    • Take one node from first half, one from reversed second half
    • Repeat until the second half is exhausted
    • The remaining nodes of the first half (if any) stay in place

Code

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        
        // Step 1: Find middle
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // Step 2: Split and reverse second half
        ListNode* second = slow->next;
        slow->next = nullptr;
        
        ListNode* prev = nullptr;
        while (second) {
            ListNode* next = second->next;
            second->next = prev;
            prev = second;
            second = next;
        }
        second = prev;  // head of reversed second half
        
        // Step 3: Merge alternately
        ListNode* first = head;
        while (second) {
            ListNode* tmp1 = first->next;
            ListNode* tmp2 = second->next;
            first->next = second;
            second->next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
};
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if not head or not head.next:
            return
        
        # Step 1: Find middle
        slow, fast = head, head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # Step 2: Split and reverse second half
        second = slow.next
        slow.next = None
        
        prev = None
        while second:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        second = prev  # head of reversed second half
        
        # Step 3: Merge alternately
        first = head
        while second:
            tmp1 = first.next
            tmp2 = second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        
        // Step 1: Find middle
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Step 2: Split and reverse second half
        ListNode second = slow.next;
        slow.next = null;
        
        ListNode prev = null;
        while (second != null) {
            ListNode next = second.next;
            second.next = prev;
            prev = second;
            second = next;
        }
        second = prev;
        
        // Step 3: Merge alternately
        ListNode first = head;
        while (second != null) {
            ListNode tmp1 = first.next;
            ListNode tmp2 = second.next;
            first.next = second;
            second.next = tmp1;
            first = tmp1;
            second = tmp2;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

Each of the three phases traverses the list (or a half of it) once:

  • Finding the middle: O(n/2) — slow pointer visits half the nodes
  • Reversing the second half: O(n/2) — we visit each node in the second half once
  • Merging the two halves: O(n/2) — we process each node pair once

Total: O(n/2) + O(n/2) + O(n/2) = O(n).

Space Complexity: O(1)

All operations are performed in-place by rearranging pointers. We use only a constant number of pointer variables (slow, fast, prev, curr, tmp1, tmp2). No arrays, stacks, or other auxiliary data structures are needed.