Reorder Linked List: L0→Ln→L1→Ln-1

The reorder list problem asks you to take a linked list L0 → L1 → L2 → ... → Ln and rearrange it into L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → .... You cannot just swap values — you must move the actual nodes. This is LeetCode 143, and the pattern behind it appears in dozens of other problems.

Why This Problem Matters

At first glance, reordering looks like it needs random access (arrays), but linked lists do not support indexing. The trick is to decompose the problem into three well-known sub-problems:

1. Find the middle — split the list into two halves
2. Reverse the second half — so you can walk it forward
3. Merge alternating — interleave nodes from each half

Each sub-problem is a classic pattern on its own. Once you master this decomposition, you can solve many “rearrange a linked list” problems by combining these building blocks.

Step-by-Step Walkthrough

Let us trace through the list 1 → 2 → 3 → 4 → 5:

Step 1: Find the Middle

Using the slow/fast pointer technique:

Initial:  slow=1, fast=1
Step 1:   slow=2, fast=3
Step 2:   slow=3, fast=5
fast.next is None → stop
Middle node: 3

We split the list:

• First half: 1 → 2 → 3
• Second half: 4 → 5

We cut the connection: node3.next = None.

Step 2: Reverse the Second Half

Before: 4 → 5 → None
After:  5 → 4 → None

Now the second half starts at node 5 and walks toward node 4.

Step 3: Merge Alternating

We take one node from each list alternately:

Take from first:  1
Take from second: 5
Take from first:  2
Take from second: 4
Take from first:  3
Result: 1 → 5 → 2 → 4 → 3

This is exactly the desired reorder.

The ListNode Class

class ListNode:
    """Standard singly linked list node."""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        parts = []
        node = self
        while node:
            parts.append(str(node.val))
            node = node.next
        return " → ".join(parts)

Finding the Middle

The slow pointer moves one step while the fast pointer moves two. When fast reaches the end, slow is at the middle:

def find_middle(head):
    """
    Return the middle node of the linked list.
    For even-length lists, returns the end of the first half.
    Time: O(n), Space: O(1)
    """
    slow = head
    fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    return slow

Why fast.next and fast.next.next? This version stops slow at the last node of the first half rather than the first node of the second half. This makes it easy to cut the list cleanly.

For a list of length 5: slow ends at index 2 (the 3rd node). For a list of length 4: slow ends at index 1 (the 2nd node).

Reversing the Second Half

Standard iterative reversal with three pointers:

def reverse_list(head):
    """
    Reverse a linked list in place.
    Time: O(n), Space: O(1)
    """
    prev = None
    current = head
    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node
    return prev  # New head of reversed list

Let us trace reversal of 4 → 5:

Step	current	prev	Action
0	4	None	Save next=5, 4.next=None, prev=4, curr=5
1	5	4	Save next=None, 5.next=4, prev=5, curr=None
Done	None	5	Return 5 (new head)

Result: 5 → 4 → None.

Merging Two Lists Alternating

This is the trickiest part. We take one node from first, then one from second, alternating:

def merge_alternating(first, second):
    """
    Merge two lists by taking nodes alternately.
    Modifies the lists in place.
    Time: O(n), Space: O(1)
    """
    while second:
        # Save next pointers
        first_next = first.next
        second_next = second.next

        # Insert second node after first node
        first.next = second
        second.next = first_next

        # Advance pointers
        first = first_next
        second = second_next

Trace with first = 1→2→3 and second = 5→4:

Step	first	second	After insertion
0	1	5	1→5→2→3, advance to first=2, second=4
1	2	4	1→5→2→4→3, advance to first=3, second=None
Done	3	None	Loop ends

Result: 1 → 5 → 2 → 4 → 3.

Complete Solution

Putting all three steps together:

def reorder_list(head):
    """
    Reorder list: L0→Ln→L1→Ln-1→L2→Ln-2→...
    LeetCode 143 — Reorder List
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return head

    # Step 1: Find the middle
    mid = find_middle(head)
    second_half = mid.next
    mid.next = None  # Cut the list

    # Step 2: Reverse the second half
    second_half = reverse_list(second_half)

    # Step 3: Merge alternating
    merge_alternating(head, second_half)

    return head

Let us test it:

def build_list(values):
    """Helper to build a linked list from a Python list."""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head


# Test with odd-length list
head = build_list([1, 2, 3, 4, 5])
print("Before:", head)  # 1 → 2 → 3 → 4 → 5
reorder_list(head)
print("After: ", head)  # 1 → 5 → 2 → 4 → 3

# Test with even-length list
head = build_list([1, 2, 3, 4])
print("Before:", head)  # 1 → 2 → 3 → 4
reorder_list(head)
print("After: ", head)  # 1 → 4 → 2 → 3

# Edge cases
head = build_list([1])
reorder_list(head)
print("Single:", head)  # 1

head = build_list([1, 2])
reorder_list(head)
print("Two:   ", head)  # 1 → 2

Why Not Use Extra Space?

You could solve this with an array or deque:

def reorder_list_deque(head):
    """
    Reorder using a deque — simpler but O(n) space.
    """
    from collections import deque
    if not head:
        return head

    # Collect all nodes
    nodes = deque()
    current = head
    while current:
        nodes.append(current)
        current = current.next

    # Rebuild by popping from both ends
    dummy = ListNode(0)
    tail = dummy
    while nodes:
        tail.next = nodes.popleft()
        tail = tail.next
        if nodes:
            tail.next = nodes.pop()
            tail = tail.next
    tail.next = None

    return dummy.next

This works, but interviewers specifically want the O(1) space solution. It tests whether you can combine multiple linked list techniques without a crutch.

Complexity Analysis

Step	Time	Space
Find middle	O(n)	O(1)
Reverse second half	O(n/2) = O(n)	O(1)
Merge alternating	O(n/2) = O(n)	O(1)
Overall	O(n)	O(1)

Each node is visited at most twice (once during find-middle, once during merge), so the total work is linear.

Common Mistakes

1. Wrong middle for even-length lists. If your find-middle returns the first node of the second half instead of the last node of the first half, you will lose nodes during the cut.

2. Forgetting to cut the list. If you do not set mid.next = None, the first half still points into the second half, creating a corrupted structure after reversal.

3. Off-by-one in merge. The first half might have one more node than the second half (for odd-length lists). Make sure your merge loop only runs while second is not None.

4. Not handling length < 3. Lists of length 0, 1, or 2 are already in reorder form. Always guard with if not head or not head.next.

Variation: Reorder from the End

Sometimes you need Ln → L0 → Ln-1 → L1 → ... (starting from the end). The approach is the same — just reverse the first half instead of the second, and start the merge from the reversed second half:

def reorder_list_from_end(head):
    """
    Reorder: Ln→L0→Ln-1→L1→...
    Time: O(n), Space: O(1)
    """
    if not head or not head.next:
        return head

    mid = find_middle(head)
    second_half = mid.next
    mid.next = None

    # Reverse the second half
    second_half = reverse_list(second_half)

    # Start merge from second half (reversed tail)
    merge_alternating(second_half, head)

    return second_half

Where This Pattern Appears

The find-middle + reverse + merge pattern is the backbone of several problems:

• Palindrome linked list (LeetCode 234) — find middle, reverse second half, compare
• Sort list (LeetCode 148) — find middle, recurse on halves, merge sorted
• Reorder list (LeetCode 143) — this problem
• Fold a linked list — same as reorder, different name

Once you internalize the three building blocks, all of these become mechanical.

Practice Problems

1. LeetCode 143 — Reorder List: The exact problem covered here (Medium)
2. LeetCode 234 — Palindrome Linked List: Uses the same find-middle + reverse pattern (Easy)
3. LeetCode 148 — Sort List: Merge sort uses find-middle + merge (Medium)
4. LeetCode 876 — Middle of the Linked List: Practice the find-middle step alone (Easy)
5. LeetCode 206 — Reverse Linked List: Practice the reversal step alone (Easy)
6. LeetCode 21 — Merge Two Sorted Lists: Practice the merge step (Easy)

Key Takeaways

• Reorder list decomposes into three classic sub-problems: find middle, reverse, merge.
• The O(1) space solution is what interviewers expect — avoid the deque approach in interviews.
• The same three-step pattern solves palindrome checking, merge sort on lists, and folding.
• Always cut the list after finding the middle to avoid pointer corruption.
• Handle edge cases (empty, single node, two nodes) before entering the main logic.