Reorder List

class Solution {
public:
    void reorderList(ListNode* head) {
        if (!head || !head->next) return;
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }
        ListNode* second = slow->next;
        slow->next = nullptr;
        // Reverse second half.
        ListNode* prev = nullptr;
        while (second) {
            ListNode* nxt = second->next;
            second->next = prev;
            prev = second;
            second = nxt;
        }
        second = prev;
        // Weave.
        ListNode* first = head;
        while (second) {
            ListNode *fNext = first->next, *sNext = second->next;
            first->next = second;
            second->next = fNext;
            first = fNext;
            second = sNext;
        }
    }
};

func reorderList(head *ListNode) {
    if head == nil || head.Next == nil {
        return
    }
    slow, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    second := slow.Next
    slow.Next = nil
    var prev *ListNode
    for second != nil {
        nxt := second.Next
        second.Next = prev
        prev = second
        second = nxt
    }
    second = prev
    first := head
    for second != nil {
        fNext, sNext := first.Next, second.Next
        first.Next = second
        second.Next = fNext
        first = fNext
        second = sNext
    }
}

from typing import Optional

class Solution:
    def reorderList(self, head: Optional[ListNode]) -> 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:
            nxt = second.next
            second.next = prev
            prev = second
            second = nxt
        second = prev
        first = head
        while second:
            f_next, s_next = first.next, second.next
            first.next = second
            second.next = f_next
            first = f_next
            second = s_next

function reorderList(head) {
    if (!head || !head.next) return;
    let slow = head, fast = head;
    while (fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    let second = slow.next;
    slow.next = null;
    let prev = null;
    while (second) {
        const nxt = second.next;
        second.next = prev;
        prev = second;
        second = nxt;
    }
    second = prev;
    let first = head;
    while (second) {
        const fNext = first.next, sNext = second.next;
        first.next = second;
        second.next = fNext;
        first = fNext;
        second = sNext;
    }
}

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode second = slow.next;
        slow.next = null;
        ListNode prev = null;
        while (second != null) {
            ListNode nxt = second.next;
            second.next = prev;
            prev = second;
            second = nxt;
        }
        second = prev;
        ListNode first = head;
        while (second != null) {
            ListNode fNext = first.next, sNext = second.next;
            first.next = second;
            second.next = fNext;
            first = fNext;
            second = sNext;
        }
    }
}

function reorderList(head: ListNode | null): void {
    if (!head || !head.next) return;
    let slow: ListNode = head;
    let fast: ListNode = head;
    while (fast.next && fast.next.next) {
        slow = slow.next as ListNode;
        fast = fast.next.next;
    }
    let second: ListNode | null = slow.next;
    slow.next = null;
    let prev: ListNode | null = null;
    while (second) {
        const nxt: ListNode | null = second.next;
        second.next = prev;
        prev = second;
        second = nxt;
    }
    second = prev;
    let first: ListNode | null = head;
    while (second) {
        const fNext: ListNode | null = (first as ListNode).next;
        const sNext: ListNode | null = second.next;
        (first as ListNode).next = second;
        second.next = fNext;
        first = fNext;
        second = sNext;
    }
}