無(wú)論是靜態(tài)鏈表還是動(dòng)態(tài)鏈表，有時(shí)在解決具體問(wèn)題時(shí)，需要我們對(duì)其結(jié)構(gòu)進(jìn)行稍微地調(diào)整。比如，可以把鏈表的兩頭連接，使其成為了一個(gè)環(huán)狀鏈表，通常稱為循環(huán)鏈表。

和它名字的表意一樣，只需要將表中最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)，鏈表就能成環(huán)兒，如圖?1 所示。

需要注意的是，雖然循環(huán)鏈表成環(huán)狀，但本質(zhì)上還是鏈表，因此在循環(huán)鏈表中，依然能夠找到頭指針和首元節(jié)點(diǎn)等。循環(huán)鏈表和普通鏈表相比，唯一的不同就是循環(huán)鏈表首尾相連，其他都完全一樣。

循環(huán)鏈表實(shí)現(xiàn)約瑟夫環(huán)

約瑟夫環(huán)問(wèn)題，是一個(gè)經(jīng)典的循環(huán)鏈表問(wèn)題，題意是：已知 n 個(gè)人（分別用編號(hào) 1，2，3，…，n 表示）圍坐在一張圓桌周圍，從編號(hào)為 k 的人開始順時(shí)針報(bào)數(shù)，數(shù)到 m 的那個(gè)人出列；他的下一個(gè)人又從 1 開始，還是順時(shí)針開始報(bào)數(shù)，數(shù)到 m 的那個(gè)人又出列；依次重復(fù)下去，直到圓桌上剩余一個(gè)人。

如圖 2 所示，假設(shè)此時(shí)圓周周圍有 5 個(gè)人，要求從編號(hào)為 3 的人開始順時(shí)針數(shù)數(shù)，數(shù)到 2 的那個(gè)人出列：

出列順序依次為：

• 編號(hào)為 3 的人開始數(shù) 1，然后 4 數(shù) 2，所以 4 先出列；

• 4 出列后，從 5 開始數(shù) 1，1 數(shù) 2，所以 1 出列；

• 1 出列后，從 2 開始數(shù) 1，3 數(shù) 2，所以 3 出列；

• 3 出列后，從 5 開始數(shù) 1，2 數(shù) 2，所以 2 出列；

• 最后只剩下 5 自己，所以 5 勝出。

約瑟夫環(huán)問(wèn)題有多種變形，比如順時(shí)針轉(zhuǎn)改為逆時(shí)針等，雖然問(wèn)題的細(xì)節(jié)有多種變數(shù)，但解決問(wèn)題的中心思想是一樣的，即使用循環(huán)鏈表。

通過(guò)以上的分析，我們可以嘗試編寫 C 語(yǔ)言代碼，完整代碼如下所示：

輸出結(jié)果：

輸入圓桌上的人數(shù):5
從第幾個(gè)人開始報(bào)數(shù)(k>1且k<5)：3
數(shù)到幾的人出列：2
出列人的編號(hào)為:4
出列人的編號(hào)為:1
出列人的編號(hào)為:3
出列人的編號(hào)為:2
出列人的編號(hào)為:5

最后出列的人，即為勝利者。當(dāng)然，你也可以改進(jìn)程序，令查找出最后一個(gè)人時(shí)，輸出此人勝利的信息。

總結(jié)

循環(huán)鏈表和動(dòng)態(tài)鏈表唯一不同在于它的首尾連接，這也注定了在使用循環(huán)鏈表時(shí)，附帶最多的操作就是遍歷鏈表。

在遍歷的過(guò)程中，尤其要注意循環(huán)鏈表雖然首尾相連，但并不表示該鏈表沒有第一個(gè)節(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。所以，不要隨意改變頭指針的指向。