My solution: O(n) running time

split the string using ' ' to string[] strs.

int len = strs.length;
int mid = len / 2;
string temp = null;
int swapIndex =0;

for(int i = 0; i {
swapIndex = len - 1 - i;
temp = strs[i];
strs[i] = str[swapIndex ];
strs[swapIndex] = temp;
}

then construct a string from the reversed array strs.

this algorithm only scans the array once to do the reversing.