Solving Reorder List in Python: Step-by-Step Guide

Introduction to the Reorder List Problem

The Reorder List problem is a classic linked list manipulation challenge frequently encountered in coding interviews and algorithm practice platforms like LeetCode. Given a singly linked list L0 → L1 → … → Ln - 1 → Ln, the task is to reorder it in-place to L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …. You may not modify the values in the list's nodes—only the next pointers themselves may be changed.

While the problem statement sounds simple, it elegantly tests multiple foundational linked list skills at once: finding the middle, reversing a list, and merging two lists. Mastering it builds a strong mental model for pointer manipulation that transfers to many real-world scenarios.

Why This Problem Matters

• Interview relevance: It combines three core operations into one problem, making it a favorite among interviewers at top tech companies.
• Pointer discipline: It forces you to carefully manage references, a skill essential for working with low-level data structures.
• In-place constraints: The O(1) extra space requirement teaches efficient memory usage.
• Real-world parallels: Reordering patterns appear in buffer management, playlist shuffling, and pagination logic.

Understanding the Problem With an Example

Suppose you are given the linked list 1 → 2 → 3 → 4 → 5. After reordering, the expected output is 1 → 5 → 2 → 4 → 3. Notice how the first node connects to the last, the second to the second-to-last, and so on, until the middle node is left at the end.

For an even-length list like 1 → 2 → 3 → 4, the result becomes 1 → 4 → 2 → 3. The middle element naturally falls into place without any special handling.

Breaking Down the Solution Strategy

The most efficient approach splits the problem into three distinct phases. Each phase is a well-known linked list operation on its own, which makes the overall solution easier to reason about and test.

Step 1: Find the Middle of the List

Use the slow and fast pointer technique. The slow pointer advances one node at a time while the fast pointer advances two. When the fast pointer reaches the end, the slow pointer will be at the middle. This runs in O(n) time and O(1) space.

Step 2: Reverse the Second Half

Starting from the middle node, reverse the second half of the list. After reversal, you will have two separate lists: the first half in original order and the second half in reversed order.

Step 3: Merge the Two Halves Alternately

Traverse both lists simultaneously, alternating nodes from the first half and the reversed second half. Adjust the next pointers carefully to avoid losing references.

Defining the Linked List Node

Before writing the solution, define the node structure. Most interview platforms provide this, but understanding it is essential.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    """Helper to build a linked list from a Python list."""
    dummy = ListNode()
    current = dummy
    for v in values:
        current.next = ListNode(v)
        current = current.next
    return dummy.next

def to_list(head):
    """Helper to convert a linked list back to a Python list."""
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

Complete Solution Implementation

Below is the full implementation combining all three steps. Each phase is isolated into its own method for clarity and testability.

class Solution:
    def reorderList(self, head):
        """
        Reorders the linked list in-place.
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return

        # Step 1: Find the middle using slow and fast pointers
        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next

        # Step 2: Reverse the second half of the list
        second = self.reverse(slow.next)
        slow.next = None  # Cut the first half from the second

        # Step 3: Merge the two halves alternately
        first = head
        while second:
            tmp1 = first.next
            tmp2 = second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

    def reverse(self, node):
        """Reverses a linked list starting at the given node."""
        prev = None
        current = node
        while current:
            nxt = current.next
            current.next = prev
            prev = current
            current = nxt
        return prev

Walking Through the Code

Let's trace the algorithm with the input 1 → 2 → 3 → 4 → 5:

• Find middle: Slow ends at node 3, fast reaches the end at node 5.
• Split: The first half becomes 1 → 2 → 3 and the second half starts at 4.
• Reverse second half: The second half becomes 5 → 4.
• Merge: Take 1 from the first, then 5 from the second, then 2, then 4, then 3. The result is 1 → 5 → 2 → 4 → 3.

Testing the Solution

Always test with multiple cases, including edge cases like empty lists, single-node lists, and even-length lists.

if __name__ == "__main__":
    sol = Solution()

    # Test 1: Odd-length list
    head1 = build_list([1, 2, 3, 4, 5])
    sol.reorderList(head1)
    print(to_list(head1))  # Output: [1, 5, 2, 4, 3]

    # Test 2: Even-length list
    head2 = build_list([1, 2, 3, 4])
    sol.reorderList(head2)
    print(to_list(head2))  # Output: [1, 4, 2, 3]

    # Test 3: Single node
    head3 = build_list([1])
    sol.reorderList(head3)
    print(to_list(head3))  # Output: [1]

    # Test 4: Two nodes
    head4 = build_list([1, 2])
    sol.reorderList(head4)
    print(to_list(head4))  # Output: [1, 2]

    # Test 5: Empty list
    head5 = build_list([])
    sol.reorderList(head5)
    print(to_list(head5))  # Output: []

Complexity Analysis

Understanding the time and space complexity is crucial for evaluating any solution.

• Time complexity: O(n). Finding the middle takes O(n), reversing the second half takes O(n/2), and merging takes O(n/2). Overall linear time.
• Space complexity: O(1). All operations are performed in-place using a constant number of pointers, regardless of the input size.

Best Practices and Common Pitfalls

Best Practices

• Modularize: Separate the reverse logic into its own method. This improves readability and makes unit testing easier.
• Use helper functions: Functions like build_list and to_list simplify testing and debugging.
• Guard against edge cases: Always check for empty lists and single-node lists before performing any pointer manipulation.
• Draw it out: Sketching the pointer movements on paper prevents subtle bugs, especially during the merge step.

Common Pitfalls

• Forgetting to cut the list: If you do not set slow.next = None after finding the middle, the first half remains connected to the reversed second half, causing infinite loops.
• Incorrect middle detection: Using while fast and fast.next instead of while fast.next and fast.next.next can shift the middle by one node, breaking the merge for even-length lists.
• Losing references during merge: Always store first.next and second.next in temporary variables before reassigning pointers.
• Modifying node values: The problem explicitly forbids changing values. Stick to pointer manipulation only.

Alternative Approaches

While the three-step approach is optimal, it is worth knowing alternatives for context.

Using a Stack

You can traverse the list once, push all nodes onto a stack, then pop from the stack while traversing again to reorder. This is simpler to implement but uses O(n) extra space, violating the in-place constraint.

def reorderListWithStack(self, head):
    if not head:
        return
    stack = []
    current = head
    while current:
        stack.append(current)
        current = current.next

    current = head
    n = len(stack) // 2
    while n > 0:
        top = stack.pop()
        nxt = current.next
        current.next = top
        top.next = nxt
        current = nxt
        n -= 1
    current.next = None

Recursive Approach

A recursive solution can also work by traversing to the end and rewiring pointers on the way back. However, recursion uses O(n) stack space and risks stack overflow for very long lists, making it impractical for production use.

Conclusion

The Reorder List problem is a powerful exercise that consolidates three essential linked list techniques into a single, elegant solution. By breaking it down into finding the middle, reversing the second half, and merging alternately, you create code that is both efficient and easy to understand. Remember to handle edge cases carefully, preserve references during pointer manipulation, and always test with lists of varying lengths. With these practices in place, you will be well-equipped to tackle this problem confidently in interviews and apply the same pointer-manipulation skills to more complex data structure challenges.