[LeetCode] Reorder List

Problem:

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:O(n)

public class Solution {
   public static void reorderList(ListNode head) {  
      if (head == null || head.next == null)  
         return;  
      ListNode slowNode = head;
      ListNode fastNode = head;  
      while (fastNode.next != null && fastNode.next.next!=null) {  
         fastNode = fastNode.next.next;    
         slowNode = slowNode.next;  
      }  
      ListNode head1 = head;
      ListNode head2 = slowNode.next;  
      slowNode.next = null;  
      ListNode cur = head2;
      ListNode post = cur.next;  
      cur.next = null;  
      while (post != null) {  
         ListNode tmp = post.next;  
         post.next = cur;  
         cur = post;  
         post = tmp;  
      }  
      head2 = cur; // the new head of the reversed sublist  
      ListNode p = head1;
      ListNode q = head2;  
      while (q != null) {  
         ListNode tmp1 = p.next;  
         ListNode tmp2 = q.next;  
         p.next = q;  
         q.next = tmp1;  
         p = tmp1;  
         q = tmp2;  
      }  
   }  
}