Reorder List

Difficulty: Medium Source: NeetCode

Problem

You are given the head of a singly linked-list: L0 → L1 → … → Ln-1 → Ln. Reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … You may not modify the values in the list’s nodes. Only nodes themselves may be changed.

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

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

Constraints:

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

Prerequisites

Before attempting this problem, you should be comfortable with:

• Slow/Fast Pointer (Middle of List) — finding the midpoint of a linked list
• Reversing a Linked List — in-place pointer reversal (see problem 1)
• Merging Two Lists — interleaving nodes from two lists

1. Brute Force / Naive Approach

Intuition

Collect all the nodes into a Python list (by reference, not by value). Then use two pointers — one from the front, one from the back — to pick nodes alternately and re-link them. This avoids the three-step trick but uses O(n) extra space.

Algorithm

1. Collect all nodes into a Python list nodes.
2. Use left = 0 and right = len(nodes) - 1 pointers.
3. While left < right:
   • Link nodes[left].next = nodes[right].
   • Advance left.
   • If left == right, break (odd-length middle node).
   • Link nodes[right].next = nodes[left].
   • Advance right backward.
4. Set nodes[left].next = None (terminate the list).

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

def reorderList_brute(head):
    if not head:
        return

    nodes = []
    cur = head
    while cur:
        nodes.append(cur)
        cur = cur.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  # terminate

# Test cases
head = build_list([1, 2, 3, 4])
reorderList_brute(head)
print("Output: ", end=""); print_list(head)  # 1 -> 4 -> 2 -> 3

head2 = build_list([1, 2, 3, 4, 5])
reorderList_brute(head2)
print("Output: ", end=""); print_list(head2)  # 1 -> 5 -> 2 -> 4 -> 3

head3 = build_list([1])
reorderList_brute(head3)
print("Output: ", end=""); print_list(head3)  # 1

Complexity

• Time: O(n) — one pass to collect, one pass to re-link
• Space: O(n) — storing all node references

2. Three-Step In-Place (Optimal)

Intuition

The key insight is that the reordering pattern is: take from the front, take from the back, alternate. That means we’re interleaving the first half with the reversed second half. So the plan is:

1. Find the middle using slow/fast pointers.
2. Reverse the second half in-place.
3. Merge the two halves by interleaving.

Let’s trace [1,2,3,4,5]:

Step 1 - Find middle:
slow/fast start at 1
slow=2, fast=3
slow=3, fast=5 (fast.next is None, stop)
Middle = node 3

First half:  1 -> 2 -> 3 -> None
Second half: 4 -> 5 -> None

Step 2 - Reverse second half:
4 -> 5 -> None  becomes  5 -> 4 -> None

Step 3 - Merge:
Take 1 from first, take 5 from second
Take 2 from first, take 4 from second
Take 3 from first (middle, second is exhausted)
Result: 1 -> 5 -> 2 -> 4 -> 3

Algorithm

1. Find the middle node using slow/fast pointers.
2. Split the list: mid.next = None terminates the first half.
3. Reverse the second half.
4. Merge first and second halves by interleaving: take one from each, alternating, until one is exhausted.

Solution

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

def build_list(values):
    if not values:
        return None
    head = ListNode(values[0])
    cur = head
    for v in values[1:]:
        cur.next = ListNode(v)
        cur = cur.next
    return head

def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result) if result else "None")

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

    # Step 1: Find the middle using slow/fast pointers
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    # slow is now the middle node

    # Step 2: Reverse the second half
    second = slow.next
    slow.next = None  # cut the list in half
    prev = None
    while second:
        tmp = second.next
        second.next = prev
        prev = second
        second = tmp
    second = prev  # second now points to the reversed second half

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

# Test cases
head = build_list([1, 2, 3, 4])
reorderList(head)
print("Output: ", end=""); print_list(head)  # 1 -> 4 -> 2 -> 3

head2 = build_list([1, 2, 3, 4, 5])
reorderList(head2)
print("Output: ", end=""); print_list(head2)  # 1 -> 5 -> 2 -> 4 -> 3

head3 = build_list([1])
reorderList(head3)
print("Output: ", end=""); print_list(head3)  # 1

head4 = build_list([1, 2])
reorderList(head4)
print("Output: ", end=""); print_list(head4)  # 1 -> 2

Complexity

• Time: O(n) — three linear passes (find middle, reverse, merge)
• Space: O(1) — all operations are in-place

Common Pitfalls

Wrong middle for even-length lists. For [1,2,3,4], the middle should be node 2 (so first half is [1,2] and second is [3,4]). Use fast.next and fast.next.next as the condition — this stops slow at node 2 for even lists.

Forgetting to cut the list in half. If you don’t set slow.next = None, the first half still connects into the second half. After reversing the second half you’ll have a messy loop.

Losing pointers during the merge. During interleaving you overwrite .next pointers. Always save first.next and second.next into temporaries before re-linking.