单向环形链表和约瑟夫问题
单向环形链表应用场景
Josephus(约瑟夫)问题
设编号为1，2，…，n个人围坐一圈约定编号为k(1<=k<=n)的人从1开始报数，数到m的那个人出列，他的下一位又从1开始报数，数到m的那个人出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列；
提示：用一个不带头节点的循环链表来处理Josephus(约瑟夫)问题，先构成一个有n个节点的单循环链表，然后由k节点起从1开始计数，计到m时，对应节点从链表中删除，然后从被删除节点的下一个节点从1开始计数，直到最后一个节点从链表中删除而结束。
举例分析
假设n=5，k=1，m=2；
约瑟夫问题模型构建
分析图解
构建环形链表思路
- 先创建第一个节点，让first指向该节点，并形成环形；
- 之后我们每创建一个新的节点，就把该节点加入到已有的环形链表中；
遍历环形链表思路
- 先让一个辅助指针(变量)指向first节点；
- 然后通过while循环遍历该环形链表即可；
curBoy.next==first;遍历结束
代码实现
代码
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
| package com.jokerdig.linkedlist;
public class Josephus {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);
circleSingleLinkedList.listBoy();
}
}
class CircleSingleLinkedList {
private Boy first = null;
public void addBoy(int nums){
if(nums < 1){
System.out.println("nums的值不正确");
return;
}
Boy curBoy = null;
for (int i = 1; i <= nums; i++) {
Boy boy = new Boy(i);
if(i==1){
first = boy;
first.setNext(first);
curBoy = first;
}else{
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
public void listBoy(){
if(first==null){
System.out.println("链表为空");
return;
}
Boy curBoy = first;
while(true){
System.out.printf("boy的编号%d \n",curBoy.getNo());
if(curBoy.getNext()==first){
break;
}
curBoy = curBoy.getNext();
}
}
}
class Boy{
private int no;
private Boy next;
public Boy(int no){
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
|
运行测试
1
2
3
4
5
6
7
| boy的编号1
boy的编号2
boy的编号3
boy的编号4
boy的编号5
Process finished with exit code 0
|
约瑟夫问题实现
分析图解
约瑟夫问题实现思路
- 需要创建一个辅助指针helper，实现指向环形链表的最后一个节点；
- 报数前，先让first和helper移动
k-1次，移动到k的位置；
- 当boy报数时，让first和helper指针同时移动
m-1次；
- 这时将first指向的节点出圈，即
first=first.next，然后helper.next=first，原本first指向的节点就没有任何引用了，会被GC回收(即出圈)；
代码实现
代码
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
139
140
141
142
143
| package com.jokerdig.linkedlist;
public class Josephus {
public static void main(String[] args) {
CircleSingleLinkedList circleSingleLinkedList = new CircleSingleLinkedList();
circleSingleLinkedList.addBoy(5);
circleSingleLinkedList.countBoy(1,2,5);
}
}
class CircleSingleLinkedList {
private Boy first = null;
public void addBoy(int nums){
if(nums < 1){
System.out.println("nums的值不正确");
return;
}
Boy curBoy = null;
for (int i = 1; i <= nums; i++) {
Boy boy = new Boy(i);
if(i==1){
first = boy;
first.setNext(first);
curBoy = first;
}else{
curBoy.setNext(boy);
boy.setNext(first);
curBoy = boy;
}
}
}
public void listBoy(){
if(first==null){
System.out.println("链表为空");
return;
}
Boy curBoy = first;
while(true){
System.out.printf("boy的编号%d \n",curBoy.getNo());
if(curBoy.getNext()==first){
break;
}
curBoy = curBoy.getNext();
}
}
public void countBoy(int startNo,int countNum,int nums){
if(first==null || startNo<1 || startNo>nums){
System.out.println("输入参数有误");
return;
}
Boy helper = first;
while(true){
if(helper.getNext()==first){
break;
}
helper = helper.getNext();
}
for(int j = 0;j<startNo-1;j++){
first = first.getNext();
helper = helper.getNext();
}
while(true) {
if (helper == first) {
break;
}
for (int i = 0; i < countNum - 1; i++) {
first = first.getNext();
helper = helper.getNext();
}
System.out.printf("boy%d出圈\n", first.getNo());
first = first.getNext();
helper.setNext(first);
}
System.out.printf("最后留在圈中的boy为%d \n",first.getNo());
}
}
class Boy{
private int no;
private Boy next;
public Boy(int no){
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
}
|
运行结果
1
2
3
4
5
6
7
| boy2出圈
boy4出圈
boy1出圈
boy5出圈
最后留在圈中的boy为3
Process finished with exit code 0
|
