Reorder List

Intuition

The target pattern alternates one node from the front with one node from the back. Reading the second half backward is exactly what a reversed second half gives us, so the problem becomes a simple alternating merge. A slow/fast pointer scan locates the midpoint in a single pass so we can cut the list cleanly into two halves. After reversing the tail portion, we zip the halves together one node at a time. Everything is done by moving pointers, so no extra list is allocated.

Algorithm walkthrough

1. 1Use slow and fast pointers so slow stops at the end of the first half when fast reaches the end.
2. 2Detach the second half by setting slow.next to null, keeping second = slow.next as its head.
3. 3Reverse the second half using the standard prev/curr pointer flip.
4. 4Set first to the original head and second to the reversed half's head.
5. 5Repeatedly splice one node from second between consecutive nodes of first, saving each next pointer before overwriting it.
6. 6Stop when the reversed half is exhausted; the list is now reordered in place.

Implementation

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        if head is None or head.next is None:
            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:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        first, second = head, prev
        while second:
            n1, n2 = first.next, second.next
            first.next = second
            second.next = n1
            first, second = n1, n2