学步园

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;
	}
}