Java环形链表实现约瑟夫环问题

简介

约瑟夫问题是个有名的问题：
N个人围成一圈，从第一个开始报数，第M个将被杀掉，最后剩下一个，其余人都将被杀掉。例如N=6，M=5，被杀掉的顺序是：5，4，6，2，3。

环形链表图解

思路分析

这里我们使用环形链表来实现，这里我用最简单的例子来分析：

• 首先我们需要一个环形链表，我们也不用太多5个节点就行，但是要首尾相连
• 同时我们需要两个指针节点，来控制报数时的移动，就比如说从第一个人开始，报2次，就相当于 第一个节点报算一次，然后第二个节点报就算第二次，那么第二个节点就被kill了

图解：

1.报数分析

2.指针移动，first指针移动到出圈节点上

3.节点出圈，然后下一次报数从出圈节点的下一个节点开始，就是first节点要后移

后面也是依此类推

代码实现

/**
 * @author 尹稳健~
 * @version 1.0
 * @time 2022/8/28
 */
public class Josepfu {
    public static void main(String[] args) {
        CircleList circleList = new CircleList();
        circleList.addNode(new AttenderNode(1));
        circleList.addNode(new AttenderNode(2));
        circleList.addNode(new AttenderNode(3));
        circleList.addNode(new AttenderNode(4));
        circleList.addNode(new AttenderNode(5));
        circleList.countNode(1,2);
    }
}

/** 环形链表 */
class CircleList{
    /** 定义头节点 */
    private final AttenderNode head = new AttenderNode(-1);

    /** 定义一个遍历节点，方便遍历 */
    AttenderNode temp;

    /** 给环形链表添加数据 */
    public void addNode(AttenderNode node){
        // 环形链表为空时，直接添加
        if (head.next == null){
            head.next = node;
            return;
        }

        temp = head.next;
        // 只有一个节点时
        while(temp.next == null){
            temp.next = node;
            node.next = head.next;
            return;
        }

        // 只有当节点的next指向head.next时，循环结束
        while (temp.next != head.next){
            temp = temp.next;
        }
        // 将节点插入到最后一个节点
        temp.next = node;
        // 并将他的next指向头节点
        node.next = head.next;
    }

    /** 打印环形链表 */
    public void showNode(){
        temp = head.next;
        // 只要节点的下一个节点不是头节点就继续打印
        while (temp.next != head.next){
            System.out.println(temp);
            temp = temp.next;
        }
        // 打印最后一个节点
        System.out.println(temp);
    }

    /** 计算环形链表中有多少个节点 */
    public int getLength(){
        int count = 0;
        temp = head.next;
        while (temp.next != head.next){
            count++;
            temp = temp.next;
        }
        count++;
        return count;
    }

    /**
     * 约瑟夫环的实现方法
     * @param startNode 从哪个节点开始
     * @param count 第几个出圈
     */
    public void countNode(int startNode,int count){
        // 定义一个头节点
        AttenderNode first = head.next;
        temp = head.next;
        // 将temp指向头节点的前一个节点
        while (true){
            if (temp.next == head.next){
                break;
            }
            temp = temp.next;
        }

        // 根据startNode，改变从哪个节点开始
        for (int i = 0; i < startNode - 1 ; i++) {
            first = first.next;
            temp = temp.next;
        }

        // 出圈
        while (true){
            // 结束
            if (temp == first){
                break;
            }
            // 根据count移动
            for (int i = 0; i < count - 1; i++) {
                first = first.next;
                temp = temp.next;
            }
            // 这时，这个first节点就是出圈的
            System.out.println(first);
            // 后移，同时让前一个节点指向first
            first = first.next;
            temp.next = first;

        }
        System.out.println("存活的节点"+temp);

    }
}

/** 定义节点 */
class AttenderNode {
    int id;
    AttenderNode next;

    @Override
    public String toString() {
        return "AttenderNode{" +
                "id=" + id +
                '}';
    }

    public AttenderNode(int id) {
        this.id = id;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

打印结果：

AttenderNode{id=2}
AttenderNode{id=4}
AttenderNode{id=1}
AttenderNode{id=5}
存活的节点AttenderNode{id=3}
1
2
3
4
5

总结

博主也是学习者，不一定是对的，有什么问题可以评论，发现错误，共同学习，谢谢大家看到最后!