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.

For example,

Given {1,2,3,4}, reorder itto {1,4,2,3}.

Considering the following steps:

 * 1. split such list into two list, first and second, according to slow and fast point

 * 2. reverse the second list

 * 3. insert the second list into the first list

coding solution:

/**

 * Definition for singly-linked list.

 * class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) {

 *         val = x;

 *         next = null;

 *     }

 * }

 *

 */

public class Solution {

    public void reorderList(ListNode head) {

        if(head!=null&&head.next!=null){

			ListNode low=head;//1. split such list into two list, first and second, according to slow and fast point

			ListNode fast=head;

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

				low=low.next;

				fast=fast.next.next;

			}

			ListNode first=head;

			ListNode second=low.next;

			low.next=null;

		    second=reverse(second);//2. reverse the second list

			while(second!=null){//3. insert the second list into the first list

				ListNode p1=first.next;

				ListNode p2=second.next;

				first.next=second;

				second.next=p1;

				first=p1;

				second=p2;

			}

		}

    }

	private ListNode reverse(ListNode head){

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

			return head;

		ListNode pre=head;

		ListNode cur=head.next;

		while(cur!=null){

			ListNode nextNode=cur.next;

			cur.next=pre;

			pre=cur;

			cur=nextNode;

		}

		head.next=null;

		return pre;

	}

}