题解 | #在二叉树中找到两个节点的最近公共祖先#

O(N), O(N)

不用库函数，分别使用双指针和快慢指针操作

新建一新方法，双指针实现字符数组翻转，然后利用快慢指针，对每一个单词进行翻转，最后进行整体的翻转

时间复杂度，(双指针操作)整体翻转 n / 2， 所有单词的翻转也近似于 n / 2 ，故时间复杂度 O(N)

public class Solution {
public String ReverseSentence(String str) {//整体翻转+局部翻转
    char[] chs = str.toCharArray();
    int slow = 0;
    
    for(int fast = 0; fast < chs.length; fast++){
        if(chs[fast] == ' '){
            reverse(chs, slow, fast - 1);//左闭右闭
            slow = fast + 1;
        }
    }
    
    reverse(chs, slow, chs.length - 1);//剩余最后一个单词的翻转
    
    reverse(chs, 0, chs.length - 1);//整体翻转
    return new String(chs);
}

public void reverse(char[] chs, int left, int right){//左闭右闭。双指针
    for(int i = left, j = right; i < j; i++, j--){
        char tmp = chs[i];
        chs[i] = chs[j];
        chs[j] = tmp;
    }
}
}