约瑟夫问题的由来

简而言之

• N个人围成一圈
• 从第M个开始报数，第K个将被杀掉
• 剩余的人重新围成圈，从被杀的下一个人开始报数，将报到K的人杀掉
• 依此循环直到剩下最后一个人
  例如N=6，M=2，K=5，被杀掉的顺序是：6、5、1、3、4、2。

解题思路

首先初始化环形单向链表并且定义两个指针一个指向链表的首结点一个指向链表的尾结点

然后确定第一个开始数数的人的位置（本题以M=2为例）

找到数到K的人（本题K=5）

杀掉数到K的人

接下里依次循环上述步骤

代码实现

public class PersonNode {
	//人的编号
    private int no;
    //指向下一个结点
    private PersonNode next;
    //构造方法
    public PersonNode(int no) {
        this.no = no;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public PersonNode getNext() {
        return next;
    }
    public void setNext(PersonNode next) {
        this.next = next;
    }
    @Override
    public String toString() {
        return "PersonNode{" +"no=" + no +'}';
    }
}

public class PersonCircleLinkList {
	//初始化首结点
    private PersonNode first = new PersonNode(-1);
    /** * 初始化单向循环链表 * @num 初始化环形链表的长度 */
    public void init(int num){
        if (num<1){
        	//链表长度小于1没有意义
            System.out.println("结点的数量不能小于1");
            return;
        }
        PersonNode temp = first;
        for (int i = 1; i <=num ; i++) {
            if(i == 1){
                //如果只有一个结点就让首结点的next指向自己
                temp.setNo(1);
                temp.setNext(first);
            }else{
            	//当环形链表长度大于2时每次循环都会创建一个结点加在链表的尾部
            	//再让尾部结点的next指向首结点
                PersonNode personNode = new PersonNode(i);
                temp.setNext(personNode);
                personNode.setNext(first);
                temp=temp.getNext();
            }
        }
    }
    /** * 遍历链表 */
    public void show(){
        if (first.getNext() == null){
            System.out.println("当前链表为空");
            return;
        }
        PersonNode temp = first;
        while(true){
            System.out.println(temp);
            if (temp.getNext() == first){
                //遍历到链表的最后一个结点
                return;
            }
            temp = temp.getNext();
        }
    }
    /** * * @param start 开始数数的人 * @param num 每次数几个数 * @param count 一共几个人参与 */
    public void killPerson(int start,int num,int count){
        init(count);
        if(first == null||start<0||num<0||start>count){
            System.out.println("参数不正确");
        }
        PersonNode last = first;
        while(true){
            if (last.getNext() == first) {
                //last指向环形链表中的最后一个元素
                break;
            }
            last = last.getNext();
        }
        //确定开始报数的位置
        for (int i = 0; i < start-1 ; i++) {
            first = first.getNext();
            last = last.getNext();
        }
        while(true){
            if (last == first){
                //只有一个结点就结束循环（剩下最后一个人）
                break;
            }
            //开始数数 for循环结束first指向数到K的人
            for (int i = 0; i < num - 1; i++) {
                first = first.getNext();
                last = last.getNext();
            }
            System.out.println(first.getNo()+"号kill");
            first=first.getNext();
            last.setNext(first);
        }
        //最后一个存活下来的人
        System.out.println(first.getNo()+"号存活");
    }
}

测试

public class PersonCircleTest {
    public static void main(String[] args) {
        PersonCircleLinkList linkList = new PersonCircleLinkList();
        linkList.killPerson(2,5,6);
    }
}

输出结果