单循环链表之约瑟夫环详解

约瑟夫环

　　先来看一个有关约瑟夫环的小故事（没兴趣的直接跳过）

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。（这里我们将所有人杀死）

画了一个约瑟夫环的示例图解：

　　　　理解起来比较容易，但是代码部分有细节需要考虑（当first指向的结点出列后，具体见下面代码分析）

　　首先2号出列

　　

　　接着第n+2个点到，也就是4号小孩出列

　　

　　以此类推，出列1号小孩

　　

 　　最终得到出列小孩依次为 2、4、1、5、3

代码部分：

　　首先构建约瑟夫环（即循环单链表）

private Boy cur=null;//这个辅助引用，代替头结点来完成循环链表的构建
private Boy first=null;//头结点
public void addBoy(int nums) {//传入多少人数
        if (nums < 2) {
            System.out.println("人数不得小于2人");
            return;
        }
        for (int i = 1; i <= nums; i++) {//遍历创建小孩结点
            Boy boy = new Boy(i);
            if (i == 1) {
                first = boy;//将第一个结点赋给first
                first.setNext(first);//形成一个环
                cur = boy;//代替头结点完成接下来的链表构建
            }
            cur.setNext(boy);//连接新结点
            boy.setNext(first);//形成环
            cur = cur.getNext();//准备连接下一个结点
        }
        cur = cur.getNext();//让cur回到头结点处，以便后序操作
    }

　　链表已经构建完成，接下来实现约瑟夫环（思路如下图）：

 　　约瑟夫环核心代码：

    /*
     * start:从第几个小孩开始报数
     * m:报数从first为1开始累计m人，则第m人出队，然后继续循环
     * nums:一共nums个小孩
     * 
     * 比如有编号为1,2,3,4,5个小孩,start为1,m为2. 则出队顺序为:2,4,1,5,3
     */
    public void countBoy(int start, int m, int nums) {
        addBoy(nums);

        Boy helper = first;

        while (true) {
            if (helper.getNext() == first)
                break;
            helper = helper.getNext();
        }
        // 从start开始报数
        for (int i = 1; i < start; i++) {//重置头结点至start处
            first = first.getNext();
            helper = helper.getNext();
        }
        while (true) {
            if (helper == first) {
                break;
            }
            System.out.println("出队编号为" + first.getNo());
            first = first.getNext();//重置头结点为出列结点的下一个结点
            helper.setNext(first);//之前first的后一个结点helper不再指向出列的结点，指向头结点
            for (int i = 1; i < m; i++) {//此处要注意上面已经喊过一次“到”，这里少一次即可
                helper = helper.getNext();
                first = first.getNext();
            }
        }
        System.out.println("出队编号为" + first.getNo());

    }