一、約瑟夫問題介紹

1、約瑟夫問題原題：

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

2、問題分析：

根據(jù)題目的描述，很容易可以想到用單向循環(huán)鏈表來模擬。先構(gòu)成一個(gè)有n個(gè)節(jié)點(diǎn)的單向循環(huán)鏈表，然后節(jié)點(diǎn)K由1開始計(jì)數(shù)，計(jì)到m時(shí)，對(duì)應(yīng)的節(jié)點(diǎn)從鏈表中刪除，然后再?gòu)谋粍h除的下一個(gè)節(jié)點(diǎn)由1開始計(jì)數(shù)，直到所有節(jié)點(diǎn)都被刪除掉。

如上圖，n等于5，假設(shè)從1號(hào)開始報(bào)數(shù)，報(bào)到2就出列，即k等于1，m等于2。那么最后出列的結(jié)果應(yīng)該是：2，4，1，5，3。

二、單向環(huán)形鏈表的構(gòu)建

1、構(gòu)建思路：

• 首先創(chuàng)建第一個(gè)節(jié)點(diǎn)，用first指針指向它，它的next指向自己，如下圖：

• 然后創(chuàng)建第二個(gè)節(jié)點(diǎn)，將第一個(gè)節(jié)點(diǎn)的next指向第二個(gè)節(jié)點(diǎn)，第二個(gè)節(jié)點(diǎn)的next指向第一個(gè)節(jié)點(diǎn)，如圖：

依此類推，就可以構(gòu)建出單向環(huán)形鏈表。遍歷的時(shí)候，當(dāng)節(jié)點(diǎn)的next等于first時(shí)，表示遍歷完畢。

2、代碼實(shí)現(xiàn)：

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

package com.zhu.study.linkedList;

/**
 * 約瑟夫問題，即單向循環(huán)鏈表問題
 * @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();
    }
}

/**
 * 單向循環(huán)鏈表
 */
class CircleSingleLinkedlist{
    private Node first = null;
    /**
     * 添加節(jié)點(diǎn)
     * @param num 需要添加的節(jié)點(diǎn)個(gè)數(shù)
     */
    public void add(int num){
        if (num < 1){
            throw new RuntimeException("非法參數(shù)");
        }
        Node cur = null; // 當(dāng)前node
        for (int i = 1; i <= num; i++) {
            Node node = new Node(i);
            if (i == 1) {
                first = node;
                first.setNext(first); // next指向自己，構(gòu)成環(huán)
                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("小孩編號(hào)%d \n", cur.getNo());
            if (cur.getNext() == first){ // 遍歷完畢
                break;
            } else {
                cur = cur.getNext();
            }
        }
    }   
}

/**
 * 節(jié)點(diǎn)內(nèi)部類
 */
class Node{
    private int no; // 編號(hào)
    private Node next; // 下一個(gè)節(jié)點(diǎn)

    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;
    }
}

三、小孩出列的實(shí)現(xiàn)

1、思路：

先要找到開始報(bào)數(shù)的節(jié)點(diǎn)，用cur記錄下來，比如從第k個(gè)開始數(shù)，那么cur應(yīng)該指向k號(hào)節(jié)點(diǎn)；然后再找到cur的前一個(gè)節(jié)點(diǎn)，用pre記錄下來；找到這兩個(gè)節(jié)點(diǎn)后，由cur開始數(shù)(m-1)次，即cur和pre同時(shí)移動(dòng)(m-1)次，此時(shí)cur就指向了要被刪除的節(jié)點(diǎn)；打印要被刪除的節(jié)點(diǎn)，然后將cur移動(dòng)到被刪除節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即cur = cur.next，pre的next指向新的cur，即pre.next = cur。

2、代碼實(shí)現(xiàn)：

/**
     * 出圈，圈中共有n個(gè)人，從第k個(gè)開始，數(shù)m個(gè)開始出圈
     * @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("非法參數(shù)");
        }
        // 先找到k節(jié)點(diǎn)，即開始報(bào)數(shù)的節(jié)點(diǎn)，用cur記錄下來
        Node cur = first;
        for (int i = 1; i < k; i++) {
            cur = cur.getNext();
        }
        // 找到k的前一個(gè)節(jié)點(diǎn)，用pre記錄下來
        Node pre = cur;
        while (true){
            if (pre.getNext() == cur){
                break;
            } else{
                pre = pre.getNext();
            }
        }
        // 出圈
        while (true) {
            if (pre == cur) { // 只有一個(gè)節(jié)點(diǎn)了
                System.out.printf("小孩編號(hào)%d\n", cur.getNo());
                break;
            }
            // cur和pre同時(shí)移動(dòng) m-1次
            for (int i = 1; i < m; i++) {
                cur = cur.getNext(); // 這個(gè)就是要出圈的節(jié)點(diǎn)
                pre = pre.getNext(); // 這個(gè)是要出圈節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
            }
            System.out.printf("小孩編號(hào)%d\n", cur.getNo());
            cur = cur.getNext();
            pre.setNext(cur);
        }
    }

調(diào)用該方法，k、m、n分別輸入1、2、5，最后發(fā)現(xiàn)結(jié)果和上面分析的一樣，打印的是2,4,1,5,3。