圆圈中最后剩下的数字

算法一，链表模拟

• 构造环形链表

• 最后循环结束的条件：只剩下一个结点，即p.next=p

• 删除结点：这里其实是做了一个等价替换，首先记录当前结点的下下个结点q，然后将下一个结点的值替换掉当前结点的值，然后删除下一个结点。等价于删除当前结点。

class Solution {
    class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
    public int lastRemaining(int n, int m) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        for (int i = 1; i < n; i++) {
            p.next = new ListNode(i);
            p = p.next;
        }
        p.next = head;
        p = head;
        int count = 1;
        while (p.next != p) {
            if (count == m) {
                ListNode q = p.next.next;
                p.val = p.next.val;
                p.next = q;
                count = 1;
            }
            p = p.next;
            count++;
        }
        return p.val;
    }
}

算法二：递归

y总讲的很好，这里就不过多赘述，因为我肯定讲的没他清楚，hhh

class Solution {
    public int lastRemaining(int n, int m) {
        if (n == 1)
            return 0;
        return (lastRemaining(n - 1,m) + m) % n;
    }
}