For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

[4, 5, 1, 2, 3]->[1, 2, 3, 4, 5]

『三步翻转法』，以[4, 5, 1, 2, 3]为例。
首先找到分割点5和1
翻转前半部分4, 5为5, 4，后半部分1, 2, 3翻转为3, 2, 1。整个数组目前变为[5, 4, 3, 2, 1]
最后整体翻转即可得[1, 2, 3, 4, 5]
由以上3个步骤可知其核心为『翻转』的in-place实现。使用两个指针，一个指头，一个指尾，使用for循环移位交换即可。

class Solution {
public:
    /*
     * @param nums: An integer array
     * @return: nothing
     */
    void recoverRotatedSortedArray(vector<int> &nums) {
        // write your code here
        for(int i = 0; i < nums.size(); i++) {
            if (nums[i+1] < nums[i]) {
                reverseA(0, i, nums);
                reverseA(i+1,nums.size()-1, nums);
                reverseA(0, nums.size()-1, nums);
            }
        }
    }

    void reverseA(int start, int end, vector<int> & nums) {
        while(start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
};