In Simple Words: 1. Find middle with fast & slow pointers. 2. Reverse second half of list. 3. Merge first half and reversed second half alternately. - Time: $O(N)$ | Space: $O(1)$ Python 3 python def reorderList(head: ListNode | ...

Q41: Reorder List. - DSA Patterns (Multi-Lang)

In Simple Words:

Find middle with fast & slow pointers.
Reverse second half of list.
Merge first half and reversed second half alternately.

Time: $O(N)$ | Space: $O(1)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

def reorderList(head: ListNode | None) -> None:
    if not head or not head.next: return
    # 1. Find middle
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    # 2. Reverse second half
    prev, curr = None, slow.next
    slow.next = None
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # 3. Interleave
    first, second = head, prev
    while second:
        tmp1, tmp2 = first.next, second.next
        first.next = second
        second.next = tmp1
        first, second = tmp1, tmp2