143

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public void ReorderList(ListNode head) {
        if (head?.next == null) return;
 
        // 1. find the middle (slow ends at the end of the first half)
        var slow = head;
        var fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
 
        // 2. cut and reverse the second half
        ListNode prev = null, curr = slow.next;
        slow.next = null;
        while (curr != null) {
            var next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
 
        // 3. merge alternately: first-half node, then second-half node
        var first = head;
        var second = prev;
        while (second != null) {
            var n1 = first.next;
            var n2 = second.next;
            first.next = second;
            second.next = n1;
            first = n1;
            second = n2;
        }
    }
}