Reverse Words in a String II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.
The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?


Naive Way:  和Reverse Words in String不同的是，这次的String是标准格式。但这次严格要求O(1)的space。因为没钱买，所以看了一下问答部分，这次它将String 改成了 char[],返回值是void。这样才能实现O(1) space，因为String是immutable的。

我想到一个简单的办法，用一头一尾交换先将整个char[] 翻转，然后对每一个单词再作内部翻转，这样就可以实现O(1) space，但是需要扫两遍。

 public class Solution{  
   public static void main(String args[]){  
     char[] s = {'t','h','e',' ','s','k','y',' ','i','s',' ','b','l','u','e'};  
     Solution ss = new Solution();  
     ss.reverseWords(s);  
     for(int i = 0;i < s.length;i++)  
       System.out.print(s[i] + " ");  
     System.out.println();  
   }  
   public void reverseWords(char[] s){  
     reverseWords(s,0,s.length-1);  
     for(int i = 0, j = 0;i <= s.length;i++){  
       if(i==s.length || s[i] == ' '){  
         reverseWords(s,j,i-1);  
         j = i+1;  
       }  
     }  
   }  
   private void reverseWords(char[] s, int begin, int end){  
     while(begin < end){  
       char c = s[begin];  
       s[begin] = s[end];  
       s[end] = c;  
       begin++;  
       end--;  
     }  
   }  
 }