题目描述

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

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

题解一

一个基本的解法是使用环形链表模拟圆圈。首先构建环形链表，然后利用一个指针在环形链表中不断地删除第m个数字。当环形链表中只剩下一个节点时，则得到结果。

这种解法需要在环形链表中遍历很多遍，删除一个节点需要m次运算，共需要遍历n遍，同时还需要一个链表来模拟圆圈。

时间复杂度为 $O(mn)$ ，空间复杂度为 $O(n)$ 。

下面是参考代码：

public int LastRemaining_Solution(int n, int m) {
    if (n == 0)
        return -1;
    // 构建环形链表。
    ListNode circle = new ListNode(-1);
    ListNode p = circle;
    for (int i = 0; i < n; i++) {
        p.next = new ListNode(i);
        p = p.next;
    }
    p.next = circle.next;

    // 利用一个指针在环形链表中不断地删除第m个数字。
    p = circle;
    while (p.next != null) {
        // 找到第m个数字的前一个数字
        for (int i = 0; i < m-1; i++)
            p = p.next;
        // 如果第m个数字不是最后一个数字，就删除第m个数字；否则将前一个数字置空
        if (p.next != p.next.next)
            p.next = p.next.next;
        else p.next = null;
    }
    return p.val;
}

题解二

也可以在题解一解法的思想上使用java的数据结构LinkedList实现。但是！！使用LinkedList的时候超时了，于是换用ArrayList试了一下，竟然通过了？按道理来说这两remove操作的时间复杂度不应该都是 $O(n)$ 吗？查了一下资料，好像是ArrayList的remove在后续移位的时候其实是内存空间的连续拷贝的，因此性能还是可以的。而LinkedList虽然删除操作的时间复杂度是 $O(1)$ ，但是在删除之前需要遍历到被删除节点的位置，这时候的时间复杂度是 $O(n)$ 。

下面是参考代码：

public int LastRemaining_Solution(int n, int m) {
    if (n == 0)
        return -1;
    LinkedList<Integer> circle = new LinkedList<>();
    // 构建环形链表
    for (int i = 0; i < n; i++)
        circle.addLast(i);

    // 删除节点
    int begin = 0;
    while (circle.size() > 1) {
        begin = (begin + m - 1) % circle.size();
        circle.remove(begin);
    }
    return circle.getFirst();
}