面试题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)。
思路2比较高级，较难理解，可遇不可求。将圆圈表示成一个函数表达式，将删除节点的过程表示成函数映射的变化，时间复杂度o(n)，空间复杂度o(1)!有兴趣的话可以搜素”约瑟夫环“去详细了解。
package chapter6;
import structure.ListNode;
/**
* Created with IntelliJ IDEA
* Author: ryder
* Date : 2017/8/20
* Time : 16:20
* Description:圆圈中最后剩下的数字
* n=5,m=3,从0,1,2,3,4组成的圆中删除第3个数字
* 依次删除3,0,4,1，最终剩下的是3
**/
public class P300_LastNumberInCircle {
public static int lastRemaining(int n,int m){
if(n<1||m<1)
return -1;
ListNode<Integer> head = new ListNode<>(0);
ListNode<Integer> cur = head;
for(int i=1;i<n;i++){
ListNode<Integer> node = new ListNode<>(i);
cur.next = node;
cur = cur.next;
}
cur.next = head;
cur = head;
while (true){
//长度为1结束循环
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;
//删除后，cur停在被删节点的后一节点处
}
}
//另一个思路分析过程较复杂，不强求了。可搜约瑟夫环进行了解。
public static void main(String[] args){
System.out.println(lastRemaining(5,3)); //3
System.out.println(lastRemaining(6,7)); //4
System.out.println(lastRemaining(0,7)); //-1
}
}
运行结果
3
4
-1
