一、约瑟夫问题介绍
1、约瑟夫问题原题：
n个小孩子手拉手围成一个圈，编号为k(1
2、问题分析：
根据题目的描述，很容易可以想到用单向循环链表来模拟。先构成一个有n个节点的单向循环链表，然后节点K由1开始计数，计到m时，对应的节点从链表中删除，然后再从被删除的下一个节点由1开始计数，直到所有节点都被删除掉。
假设从编号为1的人开始，每次报数报到2的人出列，如果有$n=5$个人，则$k=1,m=2$。那么最后出列的结果应该是：2，4，1，5，3。
立即学习“Java免费学习笔记（深入）”；
二、单向环形链表的构建
1、构建思路：
首先创建第一个节点，用first指针指向它，它的next指向自己，如下图：
接着，建立第二个节点，并将第一个节点的next指针指向第二个节点，同时将第二个节点的next指针指向第一个节点，如下图所示：
依此类推，就可以构建出单向环形链表。遍历的时候，当节点的next等于first时，表示遍历完毕。
2、代码实现：
根据上面的分析，可以写出如下代码：
<code>package com.zhu.study.linkedList;<br/><br/>/**<br/> * 约瑟夫问题，即单向循环链表问题<br/> * @author: zhu<br/> * @date: 2020/8/30 17:57<br/> */<br/>public class Josepfu {<br/> public static void main(String[] args){<br/> CircleSingleLinkedlist linkedlist = new CircleSingleLinkedlist();<br/> linkedlist.add(5);<br/> linkedlist.showNodes();<br/> }<br/>}<br/><br/>/**<br/> * 单向循环链表<br/> */<br/>class CircleSingleLinkedlist{<br/> private Node first = null;<br/> /**<br/> * 添加节点<br/> * @param num 需要添加的节点个数<br/> */<br/> public void add(int num){<br/> if (num < 1){<br/> throw new RuntimeException("非法参数");<br/> }<br/> Node cur = null; // 当前node<br/> for (int i = 1; i <= num; i++) {<br/> Node node = new Node(i);<br/> if (i == 1) {<br/> first = node;<br/> first.setNext(first); // next指向自己，构成环<br/> cur = first;<br/> } else {<br/> cur.setNext(node);<br/> node.setNext(first);<br/> cur = node;<br/> }<br/> }<br/> }<br/><br/> /**<br/> * 遍历<br/> */<br/> public void showNodes(){<br/> if (first == null){ // 链表为空<br/> return;<br/> }<br/> Node cur = first;<br/> while (true){<br/> System.out.printf("小孩编号%d \n", cur.getNo());<br/> if (cur.getNext() == first){ // 遍历完毕<br/> break;<br/> } else {<br/> cur = cur.getNext();<br/> }<br/> }<br/> } <br/>}<br/><br/>/**<br/> * 节点内部类<br/> */<br/>class Node{<br/> private int no; // 编号<br/> private Node next; // 下一个节点<br/><br/> public Node(int no){<br/> this.no = no;<br/> }<br/><br/> public int getNo() {<br/> return no;<br/> }<br/><br/> public void setNo(int no) {<br/> this.no = no;<br/> }<br/><br/> public Node getNext() {<br/> return next;<br/> }<br/><br/> public void setNext(Node next) {<br/> this.next = next;<br/> }<br/>}<br/></code>
三、小孩出列的实现
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、代码实现：
<code>/**<br/> * 出圈，圈中共有n个人，从第k个开始，数m个开始出圈<br/> * @param k<br/> * @param m<br/> * @param n<br/> */<br/> public void get(int k, int m, int n){<br/> if (k > n || k < 1 || first == null || m > n){<br/> throw new IllegalArgumentException("非法参数");<br/> }<br/> // 先找到k节点，即开始报数的节点，用cur记录下来<br/> Node cur = first;<br/> for (int i = 1; i < k; i++) {<br/> cur = cur.getNext();<br/> }<br/> // 找到k的前一个节点，用pre记录下来<br/> Node pre = cur;<br/> while (true){<br/> if (pre.getNext() == cur){<br/> break;<br/> } else{<br/> pre = pre.getNext();<br/> }<br/> }<br/> // 出圈<br/> while (true) {<br/> if (pre == cur) { // 只有一个节点了<br/> System.out.printf("小孩编号%d\n", cur.getNo());<br/> break;<br/> }<br/> // cur和pre同时移动 m-1次<br/> for (int i = 1; i < m; i++) {<br/> cur = cur.getNext(); // 这个就是要出圈的节点<br/> pre = pre.getNext(); // 这个是要出圈节点的前一个节点<br/> }<br/> System.out.printf("小孩编号%d\n", cur.getNo());<br/> cur = cur.getNext();<br/> pre.setNext(cur);<br/> }<br/> }</code>传入参数为k=1，m=2，n=5时，执行该方法的结果与上述分析相同，输出序列为2,4,1,5,3。
