Reorder List

Signal

"Interleave the front half with the reversed back half" is three linked-list primitives chained together: find the middle (fast/slow), reverse a half in place, then merge two lists by alternating nodes — each one a pattern you already have on its own.

Approach

Find the middle with slow/fast pointers, splitting the list into a front half and a back half. Reverse the back half in place. Then walk the two halves together, alternately splicing one node from the front and one from the back onto the result — since the back half is now reversed, this naturally produces the front-then-mirror ordering the problem wants.

Skeleton

slow, fast = head, head
while fast and fast.next:
    slow, fast = slow.next, fast.next.next
second = reverse(slow.next)
slow.next = None

first = head
while second:
    first.next, first = second, first.next
    second.next, second = first, second.next

Solution

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


def reorder_list(head: ListNode | None) -> None:
    if not head or not head.next:
        return

    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next

    second = slow.next
    slow.next = None
    prev = None
    while second:
        second.next, prev, second = prev, second, second.next

    first, second = head, prev
    while second:
        first.next, first = second, first.next
        second.next, second = first, second.next

Complexity

O(n) time — one pass to find the middle, one to reverse, one to merge. O(1) space — everything is re-pointed in place, no new nodes or arrays.

Pitfalls

• Off-by-one on the middle split for even-length lists — decide up front whether the front half gets the extra node and use fast.next and fast.next.next (not fast and fast.next) as the loop guard to land there consistently.
• Forgetting to cut slow.next = None before reversing the second half leaves a cycle back into the front half.
• The "dump values into an array, then rebuild" approach works and is easy to get right, but costs O(n) space — name it as the fallback, lead with the in-place three-step version.