Reorder List

Source

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.

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

Java

/**
 * 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) {  
        if(head==null || head.next==null) return;
        ListNode slow=head;
        ListNode fast=head;
        ListNode pre=null;

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

        while(slow!=null && slow.next!=null){
            ListNode tmp = slow.next.next;
            slow.next.next = pre.next;
            pre.next = slow.next;
            slow.next = tmp;
        }

        slow=head;
        fast=pre.next;
        pre.next=null;

        while(slow!=pre){
            ListNode tmp1= slow;
            slow=slow.next;
            tmp1.next=fast;
            fast=fast.next;
            tmp1.next.next=slow;
        }

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