规则

1<=m<=n

结果

image.png

完整测试代码

package com.nan;

import java.util.Queue;

/**
 * @author klr
 * @create 2020-07-03-15:37
 */

public class JosephuDemo {
    public static void main(String[] args) {
        Josephu j = new Josephu();
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        Node n6 = new Node(6);
        Node n7 = new Node(7);
        Node n8 = new Node(8);

        j.add(n1);
        j.add(n2);
        j.add(n3);
        j.add(n4);
        j.add(n5);
        j.add(n6);
        j.add(n7);
        j.add(n8);

        j.show(3,j.getNumber());
    }


}

//单向环形链表求解约瑟夫环
class Josephu{
    //不带头结点
    private Node head = null;

    public void add(Node node) {

        if (head == null) {
            head = node;
            return;
        }

        Node temp = head;
        while (temp.next!=null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    public void show(int m,int n){
        if (head == null) {
            System.out.println("环不存在");
            return;
        }
        //把单链表编程环表链表
        Node ring=head;
        while (true) {
            if (ring.next == null) {
                ring.next=head;
                break;
            }
            ring = ring.next;
        }
        int[] list = new int[n];
        int count = 1;
        int index = 0;
        Node temp = head;
        Node next = head;
        Node pre=head;
        while (n > 0) {
            if (n == 1) {
                list[index]=temp.number;
                n--;
                break;
            }
            if (count == m) {
                list[index++]=temp.number;
                next = temp.next;
                //把它从单链表中删去
                delete(temp.number,pre);
                //重新计数
                count=1;
                temp = next;
                n--;
            }
            else {
                count++;
                pre=temp;
                temp = temp.next;
            }
        }
        for (int i : list) {
            System.out.println(i);
        }
    }

    //删除结点
    public void delete(int number,Node indecate) {
        Node temp = indecate;
        if (temp == null) {
            System.out.println("该链表为空");
            return;
        }
        boolean flag = false;
        while (true) {
            if (temp.next== null) {
                break;//遍历完链表
            }
            if (temp.next.number == number) {
                flag =  true;//找到结点
                break;
            }
            temp=temp.next;
        }
        if (flag) {
            temp.next=temp.next.next;
        }
        else {
            System.out.printf("编号%d不存在",number);
        }
    }
    public int getNumber(){
        if (head == null) {
            return 0;
        }
        int count=0;
        Node temp = head;
        while (temp != null) {
            count++;
            temp=temp.next;
        }
        return count;
    }

    public Node getHead() {
        return head;
    }
}

class Node{
    public int number;
    public String description;
    public Node next;

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

    public Node(int number, String description) {
        this.number = number;
        this.description = description;
    }

    @Override
    public String toString() {
        return "Node{" +
                "number=" + number +
                ", description='" + description + '\'' +
                '}';
    }
}