39. Reorder List

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        # 1) find the middle
        slow = fast = head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        # 2) reverse the second half
        prev, curr = None, slow.next
        slow.next = None
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        # 3) weave the two halves
        a, b = head, prev
        while b:
            an, bn = a.next, b.next
            a.next, b.next = b, an
            a, b = an, bn

class Solution {
    public void reorderList(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
        ListNode prev = null, curr = slow.next;       // reverse the second half
        slow.next = null;
        while (curr != null) { ListNode nx = curr.next; curr.next = prev; prev = curr; curr = nx; }
        ListNode a = head, b = prev;                  // weave
        while (b != null) {
            ListNode an = a.next, bn = b.next;
            a.next = b; b.next = an;
            a = an; b = bn;
        }
    }
}

class Solution {
public:
    void reorderList(ListNode* head) {
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
        ListNode *prev = nullptr, *curr = slow->next;  // reverse the second half
        slow->next = nullptr;
        while (curr) { ListNode* nx = curr->next; curr->next = prev; prev = curr; curr = nx; }
        ListNode *a = head, *b = prev;                 // weave
        while (b) {
            ListNode *an = a->next, *bn = b->next;
            a->next = b; b->next = an;
            a = an; b = bn;
        }
    }
};

function reorderList(head) {
  let slow = head, fast = head;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  let prev = null, curr = slow.next; // reverse the second half
  slow.next = null;
  while (curr) { const nx = curr.next; curr.next = prev; prev = curr; curr = nx; }
  let a = head, b = prev;            // weave
  while (b) {
    const an = a.next, bn = b.next;
    a.next = b; b.next = an;
    a = an; b = bn;
  }
}