JZ46-孩子们的游戏(约瑟夫环，圆圈中最后剩下的数)

class Solution {
    public int LastRemaining_Solution(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int cur = -1;
        while (list.size() > 1) {
            for (int i = 0; i < m; i++) {
                cur++;
                if (cur == list.size()) { //转够一圈
                    cur = 0;
                }
            }
            list.remove(cur);
            cur--; //cur--的原因，因为新的list中cur指向了下一个元素，为了保证移动m个准确性，所以cur向前移动一位。
        }
        return list.get(0);
    }
}

class Solution2 {
    public int LastRemaining_Solution(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }
        ListNode head = new ListNode(0); //第一个孩子
        ListNode temp = head;
        for (int i = 1; i < n; i++) {
            temp.next = new ListNode(i);
            temp = temp.next;
        }

        temp.next = head; //形成一个环

        int k = 0;
        while (temp.next != temp) {
            if (++k == m) {
                temp.next = temp.next.next; //删去抽中的孩子
                k = 0;
            } else {
                temp = temp.next;
            }
        }
        return temp.val;
    }
}

    /**
     * f[1] = 0
     * f[2] = (f{1] + m) % 2
     * f[3] = (f[2] + m) % 3
     * ...
     * f[n] = (f[n-1] + m) % n
     */
class Solution3 {
    public int LastRemaining_Solution(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }

        int ans = 0;
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % n;
        }
        return ans;
    }
}