Leetcode 143 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.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution 1: find 2nd half, reverse it then combine with 1st half.

 public class Solution {  
   public void reorderList(ListNode head) {  
     ListNode p1=head;  
     int n=0;  
     while (p1!=null) {p1=p1.next; n++;}  
     if (n<=2) return;  
     //cut to two half  
     p1=head;  
     for (int i=0; i<(n-1)/2; i++) p1=p1.next;  
     ListNode p2=p1.next;  
     p1.next=null;  
     //reverse 2nd half  
     p1=null;  
     while (p2!=null) {  
       ListNode temp=p2.next;  
       p2.next=p1;  
       p1=p2;  
       p2=temp;  
     }  
     //combine together  
     p2=head;  
     ListNode dummy=new ListNode(0);  
     ListNode p3=dummy;  
     while (p2!=null) {  
       p3.next=p2;  
       p3=p3.next;  
       p2=p2.next;  
       if (p1!=null) {  
         p3.next=p1;  
         p3=p3.next;  
         p1=p1.next;  
       }  
     }  
     dummy.next=null;  
   }  
 }