題目

41個人排成一個圓圈，由第1個人 開始報數，每報數到第3人，該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。約瑟夫與朋友在第16與第31個位置，于是活了下來。請用單向環形鏈表描述該結構并呈現整個自殺過程。

設計

• 首先要設計一個節點模型

class Node {int value;Node next;Node(int value) {this.value = value;}}

• 遍歷并用 last 節點做成一個單向線性的鏈表，之后將自身的初始節點指向last.next 節點，扣成一個環

Node head = new Node(1);Node last = head;/** 一條單鏈數據 */for (int i = 2; i <= n; i++) {last = (last.next = new Node(i));}/**回調指向，形成環形鏈，可用如下代碼做環形鏈表是否形成的測試System.out.println(last.next.next.value);*/last.next = head;

• 遍歷每個報數到m(m=3)的節點，并重組鏈表

for (int i = 1; i < m; i++) {last = last.next; //6}/**首先以總人數3為例，再以6為例推測這段代碼，以及結合for循環就很好理解了*/last.next = last.next.next; //3、4、5

• 整個自殺鏈表遍歷的結束條件

/**以總人數 3 為例 last.next 經過遍歷為3時賦值給 last ，此時 last==last.next 是成立的，即可跳出while循環*/while (last != last.next) {for (int i = 1; i < m; i++) {last = last.next;}last.next = last.next.next;}

實現

import org.junit.Test; import static java.lang.System.out;/*** @author lorem*/ public class NodeNodeNext {class Node {int value;Node next;Node(int value) {this.value = value;}}@Testpublic void test() {winner(41, 3);}void winner(int n, int m) {Node head = new Node(1);Node last = head;/** 一條單鏈數據 */for (int i = 2; i <= n; i++) {last = (last.next = new Node(i));}/**回調指向，形成環形鏈*/last.next = head;out.println("依次死亡的序號：");while (last.value != last.next.value) {for (int i = 1; i < m; i++) {last = last.next;}out.print(last.next.value + " ");last.next = last.next.next;}out.println("\n" + "最后存活的序號：");out.printf("%d", last.value);} }

轉載于:https://www.cnblogs.com/hoodiearon/p/9693633.html

總結

以上是生活随笔為你收集整理的实现约瑟夫环形链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。