翻转单词顺序

Problem description

输入一个英文句子，翻转句子中单词的顺序，但单词内字的顺序不变。为简单起见，标点符号和普通字母一样处理。要求空间复杂度为O(1)

Examples

Example 1:
Input: I am a student.
Output: student. a am I

Solution

曾听黄工讲过这道题，当时自己的做法是，以“ ”作为分割符得到String[] str，然后用一个StringBuilder逆向遍历数组添加字符串即可。但这样空间复杂度就为O(n)
O（1）的话可以这么做，首先全部逆序一次，然后再将每个单词逆序一次即可。emmmmmm,怎么逆序单词呢？ 双指针是个好东西。双指针low,high均从0开始，默认先让high走，直至high所指向的字符为‘ ’时，逆序（low, high - 1）之间的字符，再让low = ++high;
当low所指向字符为空格时，low和high一起 ++。

Code

 void reverse(char[] s, int low, int high) {

    if (s == null || s.length <= 1 || low > high) {
        return;
    }
    char c;
    while (low < high) {
        c = s[low];
        s[low] = s[high];
        s[high] = c;
        low++;
        high--;
    }
}
String reverseSentence(char[] data) {//char比String更好处理，如果是String的话，还需要StringBuilder封装，空间复杂度为O(1)
    if (data == null || data.length <= 1) {
        return "";
    }

    int length = data.length;
    int low = 0, high = length - 1;
    reverse(data, low, high);

    high = 0;
    char begin;
    while (low < length) {
        begin = data[low];

        if (begin == ' ') {
            low++;
            high++;
        } else if (high == length || data[high] == ' ') {
            reverse(data, low, --high);
            high += 2;
            low = high;
        } else {
            high++;
        }
    }
    return data.toString();
}