剑指offer_46

题目描述:
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

自定义链表实现：

public class Solution {
    //自定义静态内部类
    static class TempLinkNode{
        int val;
        TempLinkNode next;
        TempLinkNode(int val){
            this.val=val;
        }
    }

    public static int LastRemaining_Solution(int n, int m) {
        if (n==0)return -1;//没有孩子
        TempLinkNode head=new TempLinkNode(-1);
        TempLinkNode p1=head;
        for (int i=0;i<=n-1;i++){
            TempLinkNode temp=new TempLinkNode(i);
            p1.next=temp;
            p1=p1.next;
        }
        p1.next=head.next;  //形成一个0->n-1的环，p1->始终指向当前孩子的上一个孩子:在这里指向n-1
        while (n!=1){
            // 求出当前孩子数n下,出局第k个孩子 
            // 例如：0->1->3->4->0    p1->0  k=1
            // 则出局 (孩子1)
            int k=(m%n==0 ? n : m%n);
            for (int i=1;i<=k-1;i++)
                p1=p1.next;
            p1.next=p1.next.next;//出局孩子
            n--;
        }
        return p1.next.val;
    }
}