【資料結構與算法】單向環形連結清單之【約瑟夫問題】

約瑟夫（Josephu）問題：

設編号為1，2，…，n的 n 個人圍坐一圈，約定編号為 k （1 <= k <= n）的人從 1 開始報數，數到 m 的那個人出圈，他的下一位又從 1 開始報數，數到 m 的那個人又出圈，依此類推，知道所有人出圈位置，由此産生一個出圈編号序列。

例如：下圖的出圈序列為：2 4 1 5 3

思路分析

1、根據輸入，首先生成一個環形連結清單

2、first 指針初始指向第一個結點，helper 指針初始指向最後一個結點

3、報數前，先讓 first 和 helper 指針 移動 startNo - 1 次（startNo：表示從第幾個小孩開始數數）

4、報數時，讓 first 和 helper 指針移動 countNum - 1 次（countNum：表示數幾次）

5、此時，first 指針即指向待出圈結點，而 helper 則由于始終跟在 first 指針 的後面，是以，目前 helper 指針是指向待出圈結點的前一個結點，執行：

first = first.next;

helper.next = first;

即可删除待出圈結點（準确來說是被Java的垃圾回收器自動回收）

（注：4，5 步驟在 while (true) 循環中反複執行）

代碼實作

public class Test {

    public static void main(String[] args) {
        // 測試一把看看建構環形連結清單，和周遊是否ok
        CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);// 加入5個小孩節點
        circleSingleLinkedList.showBoy();
        System.out.println("--------");
        //測試一把小孩出圈是否正确
        // 一共有5個小孩，從第1個開始報數，每數2次，就讓數到2的出來
        circleSingleLinkedList.countBoy(1, 2); // 2->4->1->5->3
    }

}

// 建立一個環形的單向連結清單
class CircleSingleLinkedList {
    // 建立一個first節點,目前沒有編号
    private Boy first = null;
    private int nums = 0;

    // 添加小孩節點，建構成一個環形的連結清單
    public void addBoy(int nums) {
        // nums 做一個資料校驗
        if (nums < 1) {
            System.out.println("nums的值不正确");
            return;
        }
        this.nums = nums;
        Boy curBoy = null; // 輔助指針，幫助建構環形連結清單
        // 使用for來建立我們的環形連結清單
        for (int i = 1; i <= nums; i++) {
            // 根據編号，建立小孩節點
            Boy boy = new Boy(i);
            // 如果是第一個小孩
            if (i == 1) {
                first = boy;
                first.next = first; // 構成環
                curBoy = first; // 讓curBoy指向第一個小孩
            } else {
                curBoy.next = boy;
                boy.next = first;
                curBoy = boy;
            }
        }
    }

    // 周遊目前的環形連結清單
    public void showBoy() {
        // 判斷連結清單是否為空
        if (first == null) {
            System.out.println("沒有任何小孩~~");
            return;
        }
        // 因為first不能動，是以我們仍然使用一個輔助指針完成周遊
        Boy curBoy = first;
        while (true) {
            System.out.printf("小孩的編号 %d \n", curBoy.no);
            if (curBoy.next == first) {// 說明已經周遊完畢
                break;
            }
            curBoy = curBoy.next; // curBoy後移
        }
    }

    /**
     * 根據使用者的輸入，計算出小孩出圈的順序
     * @param startNo 表示從第幾個小孩開始數數
     * @param countNum 表示數幾下
     */
    public void countBoy(int startNo, int countNum) {
        // 先對資料進行校驗
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("參數輸入有誤， 請重新輸入");
            return;
        }
        // 建立要給輔助指針,幫助完成小孩出圈
        Boy helper = first;
        // 需求建立一個輔助指針(變量) helper , 事先應該指向環形連結清單的最後這個節點
        while (true) {
            if (helper.next == first) { // 說明helper指向最後小孩節點
                break;
            }
            helper = helper.next;
        }
        //小孩報數前，先讓 first 和  helper 移動 startNo - 1次
        for(int j = 0; j < startNo - 1; j++) {
            first = first.next;
            helper = helper.next;
        }
        //當小孩報數時，讓first 和 helper 指針同時 的移動 countNum  - 1 次, 然後出圈
        //這裡是一個循環操作，知道圈中隻有一個節點
        while(true) {
            if(helper == first) { //說明圈中隻有一個節點
                break;
            }
            //讓 first 和 helper 指針同時 的移動 countNum - 1
            for(int j = 0; j < countNum - 1; j++) {
                first = first.next;
                helper = helper.next;
            }
            //這時first指向的節點，就是要出圈的小孩節點
            System.out.printf("小孩%d出圈\n", first.no);
            //這時将first指向的小孩節點出圈
            first = first.next;
            helper.next = first; //

        }
        System.out.printf("最後留在圈中的小孩編号%d \n", first.no);

    }
}

// 建立一個Boy類，表示一個節點
class Boy {
    public int no;// 編号
    public Boy next; // 指向下一個節點,預設null

    public Boy(int no) {
        this.no = no;
    }
}