Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

Have you met this question in a real interview? 

Yes

Example

For example,
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

/**

 * Definition for ListNode.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int val) {

 *         this.val = val;

 *         this.next = null;

 *     }

 * }

 */ 

public class Solution {

    /**

     * @param head: The head of linked list.

     * @return: void

     */

    public void reorderList(ListNode head) {  

        // write your code here

        if(head == null || head.next == null || head.next.next == null) return;

        ListNode slow = head, fast = head;

        

        while(fast.next != null && fast.next.next != null){

            fast = fast.next.next;

            slow = slow.next;

        }

        fast = slow.next;

        slow.next = null;

        // reverse

        ListNode pre = null;

        while(fast != null){

            ListNode temp = fast.next;

            fast.next = pre;

            pre = fast;

            fast = temp;

        }

        

        while(head != null && pre != null){

            ListNode temp = head.next;

            head.next = pre;

            pre = pre.next;

            head.next.next = temp;

            head = temp;

        }

        

        

    }

}