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