Given a singly linked list L: L0L1→…→Ln-1Ln,
reorder it to: L0LnL1Ln-1L2Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

/**
 * 143. Reorder List
 * https://leetcode.com/problems/reorder-list/
 * https://real-neo.me/143-reorder-list/
 */
class ReorderList {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        ListNode node = head;
        for (int i = 2; i < 10; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }

        ReorderList solution = new ReorderList();

        solution.print(head);
        solution.reorderList(head);
        solution.print(head);
    }

    private void print(ListNode node) {
        for (; node != null; node = node.next) {
            System.out.print(node.val);
            System.out.print("->");
        }
        System.out.println("null");
    }

    private void reorderList(ListNode head) {
        if (head == null || head.next == null)
            return;

        //查找到中间的节点,断开链表,进行反转
        //快慢法查找
        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //断开链表
        ListNode node = slow.next;
        slow.next = null;

        ListNode last = reverse(node);
        print(head);
        print(last);

        ListNode head1 = head;
        ListNode head2 = last;

        while (head1 != null && head2 != null) {
            ListNode n1 = head1.next;
            ListNode n2 = head2.next;
            head1.next = head2;
            head2.next = n1;
            head1 = n1;
            head2 = n2;
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = head;
        ListNode node = head.next;
        head.next = null;

        while (node != null) {
            ListNode next = node.next;
            node.next = prev;
            prev = node;
            node = next;
        }

        return prev;
    }
}