【剑指offer】孩子们的游戏(圆圈中最后剩下的数)

【建议看书上题解】
一种方法是用环形链表模拟圆圈的经典解法；

class ListNode {

    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {

    public int LastRemaining_Solution(int n, int m) {

        if (n <= 0 || m <= 0) {
            return -1;
        }

        ListNode head = new ListNode(0);
        ListNode node = head;
        for (int i = 1; i < n; i++) {
            node.next = new ListNode(i);
            node = node.next;
        }
        node.next = head;

        int k = 0;
        while (node.next != node) {
            if (++k == m) {
                node.next = node.next.next;
                k = 0;
            } else {
                node = node.next;
            }
        }

        return node.val;
    }

}

第二种是分析每次被删除数字的规律并直接计算圆圈中最后剩下的数字。

public class Solution {

    public int LastRemaining_Solution(int n, int m) {

        if (n <= 0 || m <= 0) {
            return -1;
        }

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

    }
}