1 package leetcode; 2  3 public class ReOrderList { 4     public void reorderList(ListNode head) { 5         if(head==null||head.next==null||head.next.next==null){ 6              7         }else{ 8             int l=numNode(head); 9             ListNode mid = new ListNode(-1);10             mid=getMid(head);11             ListNode next=mid.next;12             ListNode po=reverse(next);13             mid.next=null;14             ListNode p=head;15             while(po!=null){16                 ListNode po2=po.next;17                 po.next=p.next;18                 p.next=po;19                 p=p.next.next;20                 po=po2;21             }22         }23         24     }25     public int numNode(ListNode head){26         if(head==null){27             return 0;28         }29         int i=0;30         while(head!=null){31             i++;32             head=head.next;33         }34         return i;35     }36     public ListNode getMid(ListNode head){37         ListNode p=head;38         ListNode q=head;39         ListNode pre=head;40         while(q.next!=null&&q.next.next!=null){41             pre=p;42             p=p.next;43             q=q.next.next;44         }45         return p;46     }47     public ListNode reverse(ListNode n){48         ListNode h = new ListNode(-1);49         ListNode q = n;50         while(q!=null){51             ListNode next=q.next;52             q.next=h.next;53             h.next=q;54             q=next;55         }56         return h.next;57     }58     public static void main(String[] args){59         ListNode a=new ListNode(1);60         ListNode b=new ListNode(2);61         ListNode c=new ListNode(3);62         ListNode d=new ListNode(4);63         a.next=b;64         b.next=c;65         c.next=d;66         d.next=null;67         ReOrderList s = new ReOrderList();68         s.reorderList(a);69         ListNode p=a;70         while (p != null) {71             System.out.println(p.val);72             p = p.next;73         }74     }75     76 }