Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

nextPermutation.java

/*
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
*/
public class Solution {
    public void nextPermutation(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int index = num.length - 1;
        for(; index > 0; index--) {
            for(int move = index - 1; move >= 0; move--) {
                if (num[index] > num[move]) {
                    swap(num, index, move);
                    reverse(num, move+1, num.length - 1);
                    return;
                }
            }
        }
        reverse(num, 0, num.length - 1);
        return;
    }
    
    public void swap(int[] num, int right, int left){
        int tmp = num[right];
        num[right] = num[left];
        num[left] = tmp;
        return;
    }
    
    public void reverse(int[] num, int start, int end){
        int left = start;
        int right = end;
        while(right >= left){
            swap(num, right, left);
            right--;
            left++;
        }
        return;
    }
}