簡單介紹
如果把單鏈表的最后一個節點的指針指向鏈表頭部，而不是指向NULL，那么就構成了一個單向循環鏈表，通俗講就是讓尾節點指向頭結點。
單向環形鏈表應用場景：Josephu(約瑟夫、約瑟夫環)問題：
設編號為1, 2, … n的n個人圍坐一圈，約定編號為k (1<=k<=n)的人從1開始報數，數到m的那個人出列，它的下一位又從1開始報數，數到m的那個人又出列，依次類推，直到所有人出列為止，由此產生一個出隊編號的序列。
代碼實現
節點類
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
//節點類class JNode { private int id; private JNode next; public JNode(int id) { this.id = id; } public int getId() { return id; } public JNode getNext() { return next; } public void setNext(JNode next) { this.next = next; } } |
鏈表類（包括節點管理和約瑟夫環問題解決）
|
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
|
//鏈表類class CircleSingleLinkedList { private JNode first = null; //定義第一個節點，未創建時為null //添加節點，構建環形鏈表 public void add(int num) { if (num < 1){ System.out.println("創建個數不符合規定！"); return; } JNode curNode = null; //輔助變量 for (int i = 1; i <= num; i++) { JNode newNode = new JNode(i); if (i == 1){ //第一個節點較為特殊 first = newNode; //真正創建了第一個節點 first.setNext(first); //形成環狀 curNode = first; //讓輔助變量開始作用 }else { //第二個及其之后節點 curNode.setNext(newNode); //讓當前節點指向新建的節點 newNode.setNext(first); //讓新建的節點指向第一個節點，形成環狀 curNode = newNode; //更新輔助變量 } } } //遍歷鏈表 public void list(){ if (first == null){ System.out.println("鏈表為空！"); return; } JNode temp = first; while (true){ System.out.printf("取出節點%d\n",temp.getId()); if (temp.getNext() == first){ //說明已經遍歷到最后一個了 break; } temp = temp.getNext(); } } //根據參數讓節點出圈（Josepfu） public void josepfu(int startNode,int count,int num){ //startNode為開始的那個節點，count為每次數第幾個，num為鏈表節點個數 if (first == null || startNode < 1 || count < 1 || startNode > num){ System.out.println("鏈表為空或者輸入的參數不符合標準！"); return; } //讓first移動到startNode指定的節點，即移動startNode-1次 for (int i = 0; i < startNode - 1; i++) { first = first.getNext(); } //創建一個輔助變量，讓其指向最后一個節點（first前一個） JNode helper = first; while (helper.getNext() != first){ helper = helper.getNext(); } //開始按照要求出圈，每次都讓helper和first移動count-1次 while (true){ if (helper == first){ //圈中只剩下一個節點 break; } for (int i = 0; i < count - 1; i++) { first = first.getNext(); helper = helper.getNext(); } //此時first指向的即為要出圈的節點 System.out.printf("節點%d出圈\n",first.getId()); //將出圈的節點從鏈表中移除 first = first.getNext(); helper.setNext(first); } System.out.printf("節點%d為最后一個節點",first.getId()); }} |
測試類
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
/** * @Author: Yeman * @Date: 2021-10-15-22:33 * @Description: */public class JosepfuTest { public static void main(String[] args) { CircleSingleLinkedList linkedList = new CircleSingleLinkedList(); linkedList.add(5); linkedList.list(); System.out.println("==================="); linkedList.josepfu(1,2,5); }} |
到此這篇關于Java用單向環形鏈表來解決約瑟夫環Josepfu問題的文章就介紹到這了,更多相關Java 單向環形鏈表 內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/m0_46653805/article/details/120791745
