给定一个单链表 L：L₀→L₁→…→L_n-1→L_n，要求重排成：L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

不要修改节点的值，只能修改节点本身。

例一：
输入： 1->2->3->4->NULL
输出： 1->4->2->3->NULL

例二：
输入： 1->2->3->4->5->NULL
输出： 1->5->2->4->3->NULL

这个题的思路就是将链表从中间断开，然后将断开的两个链表依次连接节点。

/*
 * 143. Reorder List
 * https://leetcode.com/problems/reorder-list/
 * https://www.whosneo.com/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;
    }
}