《剑指offer》面试题62：圆圈中最后剩下的数字

题目：0，1，2…n-1这n个数字拍成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字，求剩下的最后一个数字。例如0，1，2，3，4这5个数字组成的圈，每次删除第3个数字，一次删除2，0，4，1，因此最后剩下的是3。

思路：

最直接的思路是用环形链表模拟圆圈，通过模拟删除过程，可以得到最后剩下的数字，那么这道题目就变成了删除链表中某一个节点。假设总节点数为n，删除一个节点需要走m步，那么这种思路的时间复杂度为o(mn)，空间复杂度o(n)。

java参考代码如下：

package chapter6; public class P300_LastNumberInCircle { public static class ListNode{ int val; ListNode next; public ListNode(int val){ this.val=val; this.next=null; } } public static int lastRemaining(int n,int m){ if(n<1||m<1){ return -1; } ListNode head=new ListNode(0); ListNode cur=head; for(int i=1;i<n;i++){ cur.next=new ListNode(i); cur=cur.next; } cur.next=head;//连接成环 cur=head; while (true){ if(cur.next==cur) return cur.val; for (int i=1;i<m;i++){ cur=cur.next; } cur.val=cur.next.val;//保留原节点，将下一节点值拿到，用指针跳过下一个节点，等价于删除下一节点 cur.next=cur.next.next; } } public static void main(String[] args) { System.out.println(lastRemaining(5,3));//{0,1,2,3,4}-->3 } }

参考：

圆圈中最后剩下的数字