【剑指Offer】圆圈中最后剩下的数字

题目

0, 1, …, n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

经典的解法，用环形链表模拟圆圈

public class ListNode {
    int val;
    ListNode next = null;

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

public int LastRemaining_Solution(int n, int m) {
    if (n < 1 || m < 1)
        return -1;

    ListNode head = new ListNode(0);
    ListNode tail = head;

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

    tail.next = head;
    ListNode current = head;
    ListNode prev = null;

    while (n > 1) {
        for (int i = 1; i < m; i++) {
            prev = current;
            current = current.next;
        }

        prev.next = current.next;
        current = prev.next;
        n--;
    }

    return current.val;
}

创新的解法，拿到Offer不在话下

public int LastRemaining_Solution(int n, int m) {
    if (n < 1 || m < 1)
        return -1;

    int result = 0;

    //f(n, m) = f'(n-1,m) = [f(n-1,m) + m] % n

    for (int i = 2; i <= n; i++)
        result = (result + m) % i;

    return result;
}