剑指offer第二版-62.圆圈中最后剩下的数字

本系列导航：剑指offer（第二版）java实现导航帖

面试题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