131. Reorder List

Split the list at the middle, reverse the second half, then weave the two halves together one node at a time.

Three phases

1. Find the middle with slow/fast pointers and split the list into two halves.
2. Reverse the second half in place.
3. Merge alternately: take one node from the first half, then one from the reversed second half, until the second half is exhausted.

slow = middle; second = reverse(slow.next); slow.next = None
while second: interleave first and second

Worked example

[1,2,3,4,5] → first half 1->2->3, reversed second half 5->4 → merge → 1->5->2->4->3.

Complexity

• Time: O(n).
• Space: O(1).

class Solution {
    public ListNode reorderList(ListNode head) {
        if (head == null || head.next == null) return head;
        // 1. find the middle
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 2. reverse the second half
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (second != null) {
            ListNode nxt = second.next;
            second.next = prev;
            prev = second;
            second = nxt;
        }
        // 3. merge the two halves alternately
        ListNode first = head;
        second = prev;
        while (second != null) {
            ListNode n1 = first.next, n2 = second.next;
            first.next = second;
            second.next = n1;
            first = n1;
            second = n2;
        }
        return head;
    }
}