Reorder Linked List

The Reorder List problem is a popular coding interview problem that challenges your understanding of linked list rearrangement. You're given the head of a singly linked list and asked to modify its structure to follow a specific pattern, without changing the node values. This problem is frequently asked in interviews to test your ability to perform in-place modification of data structures while maintaining time and space efficiency.

Reordering a linked list combines knowledge of node positioning, reversal, and merging techniques. While it seems simple at first glance, achieving the correct pattern in a single pass without using extra space makes this problem both challenging and insightful.

Problem Statement with Example

Given a singly linked list:

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

You need to reorder it to:

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

Example:

Input:1 → 2 → 3 → 4 → 5
Output:1 → 5 → 2 → 4 → 3

The task is not to create a new list but to modify the original list in-place, making it a perfect in-place linked list transformation problem.

How Reordering Pattern Works

This problem doesn’t just ask for reversing or sorting. Instead, it requires rearranging the nodes in an alternating pattern from both ends:

• Take the first node
• Then the last node
• Then the second node
• Then the second-last node, and so on

To clarify, you are not allowed to use any additional list or array to store the nodes. You must change the node pointerswithin the original structure.

This structure is commonly referred to as an alternating merge, and the logic is based on three sequential operations: finding the middle, reversing the second half, and mergingthe two halves.

Brute Force Approach – Using Extra Space

A simple solution that doesn't meet the constraints but helps beginners understand the logic is the brute-force method.

1. Traverse the linked list and store all nodes in an array.
2. Use two pointers to fetch nodes from both ends and reorder them alternately.
3. Reconstruct the list using updated pointers.

While this method is easier to implement, it fails the in-place constraint and uses O(n) extra space, which is not optimal for interviews.

Why it’s not recommended:

• It violates space constraints
• It doesn’t showcase optimal data structure manipulation
• Not suitable for real-world performance-critical systems

Optimal In-Place Reorder Using Three Steps

The most efficient way to solve this problem is by dividing it into three clean steps:

Step 1: Find the Middle of the Linked List

Use the fast and slow pointer technique to find the midpoint.

• The slow pointer moves one step at a time
• The fast pointer moves two steps
• When fast reaches the end, slow is at the middle

Step 2: Reverse the Second Half of the List

Starting from the middle, reverse the second half using a standard pointer-reversal technique.

1
2
3
4
5
6
7
8
def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

Step 3: Merge the Two Halves Alternately

Now that we have:

• First half in original order
• Second half in reversed order

We merge them one by one from each list:

1
2
3
4
5
6
7
def merge(l1, l2):
    while l2:
        tmp1, tmp2 = l1.next, l2.next
        l1.next = l2
        l2.next = tmp1
        l1 = tmp1
        l2 = tmp2

Python Code for Optimal Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reorderList(head):
    if not head or not head.next:
        return

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

    # Step 2: Reverse second half
    second = reverse(slow.next)
    slow.next = None  # Cut the list in half

    # Step 3: Merge the halves
    first = head
    merge(first, second)

def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

def merge(l1, l2):
    while l2:
        tmp1, tmp2 = l1.next, l2.next
        l1.next = l2
        l2.next = tmp1
        l1 = tmp1
        l2 = tmp2

This code runs in O(n) timeand O(1) space, making it optimal and fully compliant with constraints.

Time and Space Complexity

• Time Complexity:
  • Finding the middle: O(n)
  • Reversing: O(n)
  • Merging: O(n)
  • Total: O(n)
• Space Complexity:
  • No extra space used apart from pointers
  • Total: O(1)

Edge Cases and Common Mistakes

• List with only one or two nodes – No reordering needed
• Forgetting to disconnect the first half – May cause infinite loops
• Merging pointers incorrectly – Can cause broken or cyclic list
• Null pointer issues – Always check if the node exists before accessing .next

Real-Worl

• Reordering log streams or data for alternating processing
• Interleaving tasks in round-robin scheduling systems
• UI rendering where elements need to appear from ends inward (e.g., carousel sliders)

These examples showcase how linked list transformations are not just academic but have real-world applications.

Conclusion

The Reorder List problem is a perfect example of combining multiple linked list techniques like finding the midpoint, reversing, and merging. It tests your ability to write in-place solutions, work with node references, and maintain performance.

Whether you're preparing for a coding interview, building your data structure foundation, or simply exploring linked list rearrangement, this problem helps you grow into a more confident and skilled programmer.