有 n 只猴子围成一圈，从 1~n 编号，大家决定从中选出一个大王。经过协商，决定选大王的规则为：从编号为1的猴子开始报数，报到k的猴子出圈，然后再从下一只开始继续报1到k……最后剩下来的那一只就是大王。要求编程从键盘输入 n、k，输出成为大王的猴子编号。

一行两个正整数 n 和 k，2≤n≤1000，2≤k≤10⁹ 。

一行一个正整数，代表猴王的编号。

    本题采用“模拟”法实现。可以定义一个一维数组来模拟猴子在不在圈内，用 a[i] 代表第 i 只猴子的状态，0 代表出圈，1 代表在圈内。然后不断的扫描这个一维数组，如果猴子在圈内，则计数器加 1；如果不在就不加，当计数器到达 k 时，就把当前这只猴子标志出圈，然后作出一些相关的处理；当还剩一只猴子的时候就停止操作，输出剩下的圈内这只猴子的编号。
以上算法的最大问题是，如果猴子数比较多，不断扫描一维数组的时候会很慢，特别是当大部分猴子都已经出圈，会扫描很多无猴子的“无效”操作。如果建立一个循环链表，那么在扫描的时候就不会出现无猴子还扫描的情况，在猴子出圈的时候只需要在链表中删除一个元素，这样效率会提高很多。
    具体操作如下：定义一个结构体 monkey，里面有两个参数，一个代表猴子编号，另一个记录这只猴子的下一只猴子的编号，注意一开始每只猴子的下一只猴子的编号是本身的编号加 1，最后一只猴子的下一只猴子的编号是 1 号。
如果需要删除 3 号猴子，那么只需要把当前 3 号猴子前一只猴子 2 号的下一只猴子序号，指向当前猴子 3号的下一只猴子序号 4。

基本数据结构