class Solution {
    // 876 基础上改进，找到中点之后并切断
    public ListNode middleNode(ListNode head) {
        if (head == null) return null;
        ListNode slowPrev = null;
        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null) {
            slowPrev = slow;
            slow = slow.next;
            fast = fast.next;
            if (fast.next == null) break;
            fast = fast.next;
        }
        slowPrev.next = null;
        return slow;
    }

    // 标准的反转单链表
    public ListNode reverse(ListNode head) {
        ListNode left = null;
        ListNode right = head;
        while (right != null) {
            ListNode newRight = right.next;
            right.next = left;
            left = right;
            right = newRight;
        }
        return left;
    }

    public void reorderList(ListNode head) {
        if (head == null || head.next == null) return;
        ListNode middle = reverse(middleNode(head));
        ListNode sentry = new ListNode(0);
        ListNode p = sentry;
        ListNode h = head;
        ListNode m = middle;
        // head 一定比 middle 链表短
        while (h != null) {
            p.next = h;
            h = h.next;
            p = p.next;

            p.next = m;
            m = m.next;
            p = p.next;
        }
        head.next = sentry.next.next;
    }
}