Reorder List Algorithm Solution

The reorder list problem requires rearranging a singly linked list by splitting it into two halves and interleaving the nodes in reverse order. This classic algorithm demonstrates advanced linked list manipulation techniques.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. Can we modify the input list in-place, or do we need to return a new reordered list?
2. What is the expected time complexity constraint? Are we aiming for O(n) or O(n log n)?
3. What is the maximum size of the input list? Will it be small (e.g., < 100 elements) or potentially large?
4. Are duplicates allowed in the list? How should we handle them?
5. Should we preserve the original order of elements within each half when reordering?

Restatement in my own words: We are given a singly linked list and need to reorder it such that the nodes alternate between the first half and second half of the original list. Specifically, if we have a list of size n, we want to rearrange it so that the first node stays first, the last node becomes second, the second node becomes third, and so on.

Clarification of inputs, outputs, and constraints:

• Input: A singly linked list head node (ListNode)
• Output: The same list reordered in-place (no return needed)
• Constraints:
  • List can have 0 to 5×10^4 nodes
  • Node values are in range [-1000, 1000]
  • Must be done in O(1) extra space (in-place)
  • Time complexity should ideally be O(n)

Assumptions I'm making:

• The input list is valid and properly connected
• We can modify the original list structure in-place
• The reorder pattern is: 1st node, last node, 2nd node, second-to-last node, etc.
• The list can be empty or have odd/even number of nodes

Data shape and hidden structure: The problem presents a singly linked list where each node has a value and pointer to next node. The key insight is that we're essentially splitting the list into two halves, reversing one half, and then merging them alternately. The hidden structure is that we're looking for a specific interleaving pattern between two subsequences of the original list.

2. Pattern Recognition

Identifying the pattern

This problem exhibits the "Middle of the List" pattern combined with "Reverse Linked List" and "Merge Two Sorted Lists" patterns.

Wording that signals the pattern

• "Reorder the list" - suggests we need to rearrange nodes in a specific sequence
• The requirement to interleave first half with reversed second half signals a classic two-pointer approach with list reversal
• The constraint that we must reorder in-place suggests we're dealing with a structural transformation rather than data manipulation

Why this fits the pattern

The core insight is that we're essentially splitting a linked list into two halves, reversing the second half, and then merging them alternately. This is a well-known pattern in linked list manipulation problems where:

1. We need to find the middle of the list (classic two-pointer technique)
2. We need to reverse a portion of the list
3. We need to merge two lists in an alternating fashion

Core insight

The key insight is that we don't need to create new nodes or use extra space for storing values. We can manipulate the existing node pointers to achieve the desired reordering in O(1) extra space.

This pattern appears frequently in interviews because it combines multiple fundamental linked list operations (finding middle, reversing, merging) into a single cohesive problem that tests both algorithmic thinking and implementation skills.

3. Approach Evolution

My first instinct is to think about how to rearrange the list nodes in-place, which suggests we need to find a way to split and merge lists. But that's O(n²) because if I try to find the middle element by traversing from the beginning each time, that's inefficient.

Let me think about how to optimize this. I notice that if I can find the middle of the list and reverse the second half, I can then merge these two halves in an interleaved fashion. This approach would be O(n) time and O(1) space, which is optimal.

The key insight is that we want to reorder the list such that nodes from the second half are inserted between nodes from the first half. So if we have 1->2->3->4->5, we want to get 1->5->2->4->3.

I'll use the classic "slow and fast pointer" technique to find the middle, then reverse the second half, and finally merge the two halves.

My approach will be:

1. Find the middle of the list using slow/fast pointers
2. Split the list at the middle
3. Reverse the second half of the list
4. Merge the first half with the reversed second half in alternating fashion

This is an O(n) time solution that uses only constant extra space, which is optimal for this problem.

The key invariant I need to maintain is that when merging, I always take one node from the first half and one from the reversed second half in alternating fashion. This ensures proper reordering.

The approach is clean, efficient, and handles all edge cases properly including odd-length lists where the middle element gets placed correctly in the reordered sequence.

4. Data Structure Choice

For this problem, I'll use a combination of data structures to achieve an optimal solution:

Primary Data Structures:

1. Singly Linked List - The input structure itself, which we need to reorder in-place
2. Stack - To store the second half of nodes for reverse traversal
3. Pointers (slow/fast) - For finding the middle node efficiently

Why Each Data Structure Is Needed:

The stack is essential because it naturally reverses the order of elements. When we push the second half of the list onto a stack, we can easily pop nodes in reverse order to interleave them with the first half.

The slow/fast pointer technique is crucial for finding the midpoint without needing to calculate list length first. This approach uses O(1) space and O(n) time, which is optimal for this subproblem.

Time and Space Impact:

• Stack operations (push/pop) are O(1) time and O(n/2) = O(n) space in the worst case
• The slow/fast pointers use O(1) space and O(n) time for finding the midpoint
• Overall space complexity remains O(n) due to stack usage, but this is necessary for the interleaving approach

Helper Structures:

I'm not using any additional helper structures beyond what's necessary for the algorithm. The stack serves as both a storage mechanism and a way to reverse traversal order, minimizing extra data structures.

The stack approach elegantly handles the reordering requirement by allowing us to process nodes from the end of the second half backward, which is exactly what we need for the "reorder" operation. This avoids complex pointer manipulation that would be required if we tried to do everything in-place with just the original list structure.

5. Algorithm Walkthrough

Let me trace through the algorithm with the example list: [1,2,3,4,5]

Step 1: Find the middle of the list using slow/fast pointers.

• Slow starts at 1, Fast starts at 1
• Iteration 1: Slow moves to 2, Fast moves to 3
• Iteration 2: Slow moves to 3, Fast moves to 5
• Since Fast.next is null, Slow is at node 3 (middle)

Step 2: Split the list into two halves.

• First half: [1,2,3]
• Second half: [4,5] (starting from node 4)

Step 3: Reverse the second half.

• Reverse [4,5] → [5,4]

Step 4: Merge the two halves alternately.

• First half: [1,2,3]
• Second half (reversed): [5,4]
• Merge process:
  • Take 1 from first half
  • Take 5 from second half → [1,5]
  • Take 2 from first half
  • Take 4 from second half → [1,5,2,4]
  • Take 3 from first half → [1,5,2,4,3]

The algorithm correctly reorders the list to [1,5,2,4,3].

Edge case handling:

• For even-length lists like [1,2,3,4], the middle is found correctly at node 3
• For single element [1], no reordering occurs since second half is empty
• For two elements [1,2], middle is at node 1, second half is [2], reverse gives [2], merge gives [1,2]

The algorithm terminates correctly because:

1. The slow/fast pointer approach guarantees finding the true middle
2. The reversal and merging steps handle all remaining nodes
3. The loop conditions ensure we don't process beyond the valid bounds

6. Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        // Step 1: Find the middle of the list
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Step 2: Reverse the second half
        ListNode secondHalf = reverseList(slow.next);
        slow.next = null; // Break the list into two halves
        
        // Step 3: Merge the two halves
        ListNode firstHalf = head;
        while (secondHalf != null) {
            // Store next nodes before overwriting
            ListNode firstNext = firstHalf.next;
            ListNode secondNext = secondHalf.next;
            
            // Reorder: connect first half to second half
            firstHalf.next = secondHalf;
            secondHalf.next = firstNext;
            
            // Move pointers forward
            firstHalf = firstNext;
            secondHalf = secondNext;
        }
    }
    
    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
        
        return prev;
    }
}

This solution uses the classic three-step approach:

1. Find the middle using slow/fast pointers
2. Reverse the second half of the list
3. Merge the two halves by alternating nodes

The implementation carefully handles the pointer reordering to avoid losing references during the merge process. The reverseList helper method uses the standard iterative approach with three pointers to reverse a linked list in-place.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm makes three distinct passes through the list:

1. Finding the middle node: O(n/2) = O(n)
2. Reversing the second half: O(n/2) = O(n)
3. Merging the two halves: O(n/2) = O(n)

Since all operations are linear in the input size, the overall time complexity is O(n).

Space Complexity: O(1)

The solution uses only a constant amount of extra space for pointers and temporary variables. No additional data structures like arrays, stacks, or queues are created that scale with input size. The reversal is done in-place, and we only maintain a few node references throughout the process.

Why These Bounds Are Correct:

The O(n) time bound is optimal for this problem because we must examine each node at least once to reorder them properly. Any algorithm that solves this problem must touch every node in the list, making linear time unavoidable.

The O(1) space bound is achieved by leveraging the existing linked list structure rather than creating new data structures. We only use a fixed number of pointers (current, next, prev, slow, fast) regardless of input size, making the space complexity constant.

The solution is optimal because it achieves the theoretical lower bound for both time and space complexity for this problem - we cannot do better than O(n) time to process all elements, and we cannot use less than O(1) space when working with the given linked list structure.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty list: Handle gracefully with head == null check
• Single node: List with one element should remain unchanged
• Two nodes: Should reorder to [node1, node2] → [node2, node1] which is effectively no change in order

Duplicate Values and Repeated States

• The algorithm works correctly with duplicate values since it operates on structural reordering, not value comparison
• When nodes have same values, the reordering preserves their relative positions in the original list

Boundary Conditions

• Even-length lists: Need to ensure middle point calculation is correct (e.g., for 4 nodes, split at position 2)
• Odd-length lists: Middle node should be moved to the second half, not duplicated
• List with exactly 3 nodes: Should become [1,2,3] → [1,3,2]

Common Implementation Mistakes

• Not properly disconnecting the first half: Failing to set slow.next = null causes cycles in the list
• Incorrect middle point calculation: Using fast != null instead of fast.next != null can cause wrong splits
• Missing null checks: Accessing .next without checking if node is null leads to NullPointerException
• Modifying input list incorrectly: Not preserving original node references or changing the actual node values instead of structure
• Failing to handle the case where we have exactly 2 nodes: The reordering logic must correctly handle this edge case

Implementation-specific Pitfalls

• Not clearing the reference properly: When splitting, ensure slow.next = null to prevent cycles
• Incorrect stack handling in the merge: Mismanaging the order of nodes when merging creates wrong output
• Overcomplicating the reversal logic: Using an unnecessarily complex approach to reverse second half instead of simple iterative reversal

The key is to always validate that the list structure remains intact and that we're only modifying pointers, not node values.

9. Alternative Approaches

There are several alternative approaches to solving the reorder list problem, each with different trade-offs:

Approach 1: Array-based Reordering Store all list nodes in an array, then reorder them by index mapping. This approach uses O(n) extra space but can be simpler to implement and debug. The reordering logic becomes straightforward array indexing, though it requires two passes through the data.

Approach 2: Stack-based Reordering Use a stack to reverse the second half of the list, then interleave nodes from the original first half and the reversed second half. This approach maintains O(n) time but uses O(n/2) extra space for the stack, which is still O(n) space complexity.

Approach 3: Recursive Splitting Recursively split the list in half and then merge them in alternating fashion. This approach is more complex to implement correctly, requiring careful handling of the base cases and maintaining proper links. It's also harder to reason about the space complexity due to recursion stack usage.

Approach 4: Three-pass Solution with Extra Space First pass stores all nodes in a list, second pass reverses the second half, third pass interleaves the halves. This is more readable but uses O(n) space and requires multiple passes through the data.

The chosen solution using fast/slow pointers is preferred because it:

1. Uses O(1) extra space (constant space complexity)
2. Requires only one pass through the list for splitting
3. Has clean, readable logic that's easy to maintain
4. Is optimal in both time and space complexity

The stack-based approach is more intuitive but uses additional space, while the array-based approach trades simplicity for extra memory usage. The recursive approach adds complexity without significant benefit in this case.

10. Test Cases

// Test case 1: Basic case with odd number of nodes
// Input: [1,2,3,4,5] 
// Expected output: [1,5,2,4,3]
@Test
public void testOddLengthList() {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);
    
    reorderList(head);
    // Verify the reordered list matches expected pattern
    assertListEquals(new int[]{1,5,2,4,3}, head);
}

// Test case 2: Basic case with even number of nodes
// Input: [1,2,3,4,5,6]
// Expected output: [1,6,2,5,3,4]
@Test
public void testEvenLengthList() {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);
    head.next.next.next.next.next = new ListNode(6);
    
    reorderList(head);
    // Verify the reordered list matches expected pattern
    assertListEquals(new int[]{1,6,2,5,3,4}, head);
}

// Test case 3: Single node
// Input: [1]
// Expected output: [1]
@Test
public void testSingleNode() {
    ListNode head = new ListNode(1);
    
    reorderList(head);
    assertListEquals(new int[]{1}, head);
}

// Test case 4: Two nodes
// Input: [1,2]
// Expected output: [1,2]
@Test
public void testTwoNodes() {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    
    reorderList(head);
    assertListEquals(new int[]{1,2}, head);
}

// Test case 5: Empty list
// Input: []
// Expected output: []
@Test
public void testEmptyList() {
    reorderList(null);
    assertNull(null);
}

// Test case 6: Duplicate values
// Input: [1,2,2,3]
// Expected output: [1,3,2,2]
@Test
public void testDuplicateValues() {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(2);
    head.next.next.next = new ListNode(3);
    
    reorderList(head);
    assertListEquals(new int[]{1,3,2,2}, head);
}

// Helper method to verify list contents
private void assertListEquals(int[] expected, ListNode head) {
    ListNode current = head;
    int index = 0;
    
    while (current != null && index < expected.length) {
        assertEquals(expected[index], current.val);
        current = current.next;
        index++;
    }
    
    assertNull(current); // Ensure we've consumed all nodes
    assertEquals(expected.length, index);
}

The test cases cover:

1. Odd-length lists - Tests the core reordering logic with an odd number of elements
2. Even-length lists - Tests the reordering pattern for even-length inputs
3. Edge cases - Single node and empty list scenarios
4. Boundary conditions - Two-node case that should remain unchanged
5. Duplicate handling - Values that appear multiple times in the list

Each test case uses a helper method assertListEquals to verify that the reordered list matches the expected pattern. The tests ensure that our solution handles all valid inputs correctly and maintains the required reordering behavior where elements are interleaved from both ends of the original list.

11. Final Summary

The core insight is to split the linked list into two halves, reverse the second half, and then merge the two halves alternately to achieve the required reordering. This approach works because it leverages the natural structure of the problem - we want to interleave first half elements with reversed second half elements, which can be efficiently accomplished through three well-defined operations: finding the middle, reversing, and merging.

The solution is optimal with O(n) time complexity and O(1) space complexity, making it ideal for large inputs where memory constraints matter. The key efficiency comes from avoiding extra space for storing nodes and performing all operations in-place through careful pointer manipulation.

What makes this solution particularly strong is its clean separation of concerns - each phase (split, reverse, merge) has a clear purpose and can be reasoned about independently, making the code both readable and maintainable while achieving the best possible performance characteristics for this problem.