題目來(lái)自?尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫(xiě)在前面：本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會(huì)偶爾插入自己的注釋和理解，盡量會(huì)完成作業(yè)

4.5單向環(huán)形鏈表應(yīng)用場(chǎng)景

Josephu (約瑟夫，約瑟夫環(huán)) 問(wèn)題

Josephu問(wèn)題為:設(shè)編號(hào)為1，2…n的n個(gè)人圍坐一圈，約定編號(hào)為k ( 1<=k<=n)的人從1開(kāi)始報(bào)數(shù)，數(shù)到m 的那個(gè)人出列，它的下一位又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列，依次類推，直到所有人出列為止，由此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列。

提示:用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來(lái)處理Josephu問(wèn)題:先構(gòu)成一個(gè)有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表，然后由k結(jié)點(diǎn)起從1開(kāi)始計(jì)數(shù)，計(jì)到m時(shí)，對(duì)應(yīng)結(jié)點(diǎn)從鏈表中刪除，然后再?gòu)谋粍h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又從1開(kāi)始計(jì)數(shù)，直到最后一個(gè)結(jié)點(diǎn)從鏈表中刪除算法結(jié)束。

4.6單項(xiàng)環(huán)形鏈表介紹

4.7Josephu問(wèn)題

約瑟夫問(wèn)題的示意圖(使用單項(xiàng)環(huán)形鏈表完成)

Josephu問(wèn)題

Josephu問(wèn)題為:設(shè)編號(hào)為1，2，… n的n個(gè)人圍坐一圈，約定編號(hào)為k(1<=k<=n)的人從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人出列，它的下一位又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列，依次類推，直到所有人出列為止，由此產(chǎn)生一個(gè)出隊(duì)編號(hào)的序列。

提示

用一個(gè)不帶頭結(jié)點(diǎn)的循環(huán)鏈表來(lái)處理Josephu問(wèn)題:先構(gòu)成一個(gè)有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表，然后由k結(jié)點(diǎn)起從1開(kāi)始計(jì)數(shù)，計(jì)到m時(shí)，對(duì)應(yīng)結(jié)點(diǎn)從鏈表中刪除，然后再?gòu)谋粍h除結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)又從1開(kāi)始計(jì)數(shù)，直到最后一個(gè)結(jié)點(diǎn)從鏈表中刪除算法結(jié)束。

約瑟夫問(wèn)題-創(chuàng)建環(huán)形鏈表的思路圖解

約瑟夫問(wèn)題-小孩出圈的思路分析圖

4.8約瑟夫問(wèn)題的代碼實(shí)現(xiàn)

寫(xiě)給今后忘記這題的我：那么你回想起來(lái)了嗎？