一、約瑟夫問題介紹

1、約瑟夫問題原題：

n個小孩子手拉手圍成一個圈，編號為k(1 <= k <= n )的人從1開始報數，報到m的那個人出列，它的下一位又從1開始報數，報到m的又出列……依此類推，直到所有人都出列，由此產生一個出隊編號的序列。

2、問題分析：

根據題目的描述，很容易可以想到用單向循環鏈表來模擬。先構成一個有n個節點的單向循環鏈表，然后節點K由1開始計數，計到m時，對應的節點從鏈表中刪除，然后再從被刪除的下一個節點由1開始計數，直到所有節點都被刪除掉。

如上圖，n等于5，假設從1號開始報數，報到2就出列，即k等于1，m等于2。那么最后出列的結果應該是：2，4，1，5，3。

二、單向環形鏈表的構建

1、構建思路：

• 首先創建第一個節點，用first指針指向它，它的next指向自己，如下圖：

• 然后創建第二個節點，將第一個節點的next指向第二個節點，第二個節點的next指向第一個節點，如圖：

依此類推，就可以構建出單向環形鏈表。遍歷的時候，當節點的next等于first時，表示遍歷完畢。

2、代碼實現：

根據上面的分析，可以寫出如下代碼：

package com.zhu.study.linkedList;

/**
 * 約瑟夫問題，即單向循環鏈表問題
 * @author: zhu
 * @date: 2020/8/30 17:57
 */
public class Josepfu {
    public static void main(String[] args){
        CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();
        linkedlist.add(5);
        linkedlist.showNodes();
    }
}

/**
 * 單向循環鏈表
 */
class CircleSingleLinkedlist{
    private Node first = null;
    /**
     * 添加節點
     * @param num 需要添加的節點個數
     */
    public void add(int num){
        if (num < 1){
            throw new RuntimeException("非法參數");
        }
        Node cur = null; // 當前node
        for (int i = 1; i <= num; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                first.setNext(first); // next指向自己，構成環
                cur = first;
            } else {
                cur.setNext(node);
                node.setNext(first);
                cur = node;
            }
        }
    }

    /**
     * 遍歷
     */
    public void showNodes(){
        if (first == null){ // 鏈表為空
            return;
        }
        Node cur = first;
        while (true){
            System.out.printf("小孩編號%d \n", cur.getNo());
            if (cur.getNext() == first){ // 遍歷完畢
                break;
            } else {
                cur = cur.getNext();
            }
        }
    }   
}

/**
 * 節點內部類
 */
class Node{
    private int no; // 編號
    private Node next; // 下一個節點

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

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

三、小孩出列的實現

1、思路：

先要找到開始報數的節點，用cur記錄下來，比如從第k個開始數，那么cur應該指向k號節點；然后再找到cur的前一個節點，用pre記錄下來；找到這兩個節點后，由cur開始數(m-1)次，即cur和pre同時移動(m-1)次，此時cur就指向了要被刪除的節點；打印要被刪除的節點，然后將cur移動到被刪除節點的下一個節點，即cur = cur.next，pre的next指向新的cur，即pre.next = cur。

2、代碼實現：

/**
     * 出圈，圈中共有n個人，從第k個開始，數m個開始出圈
     * @param k
     * @param m
     * @param n
     */
    public void get(int k, int m, int n){
        if (k > n || k < 1 || first == null || m > n){
            throw new IllegalArgumentException("非法參數");
        }
        // 先找到k節點，即開始報數的節點，用cur記錄下來
        Node cur = first;
        for (int i = 1; i < k; i++) {
            cur = cur.getNext();
        }
        // 找到k的前一個節點，用pre記錄下來
        Node pre = cur;
        while (true){
            if (pre.getNext() == cur){
                break;
            } else{
                pre = pre.getNext();
            }
        }
        // 出圈
        while (true) {
            if (pre == cur) { // 只有一個節點了
                System.out.printf("小孩編號%d\n", cur.getNo());
                break;
            }
            // cur和pre同時移動 m-1次
            for (int i = 1; i < m; i++) {
                cur = cur.getNext(); // 這個就是要出圈的節點
                pre = pre.getNext(); // 這個是要出圈節點的前一個節點
            }
            System.out.printf("小孩編號%d\n", cur.getNo());
            cur = cur.getNext();
            pre.setNext(cur);
        }
    }

調用該方法，k、m、n分別輸入1、2、5，最后發現結果和上面分析的一樣，打印的是2,4,1,5,3。