前言

以專題的形式更新刷題貼，歡迎跟我一起學習刷題，相信我，你的堅持，絕對會有意想不到的收獲。每道題會提供簡單的解答，如果你有更優(yōu)雅的做法，歡迎提供指點，謝謝

10年積累的成都網(wǎng)站制作、網(wǎng)站設計經(jīng)驗，可以快速應對客戶對網(wǎng)站的新想法和需求。提供各種問題對應的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡服務。我雖然不認識你，你也不認識我。但先網(wǎng)站設計后付款的網(wǎng)站建設流程，更有永和免費網(wǎng)站建設讓你可以放心的選擇與我們合作。

【題目描述】

【要求】

輸入：一個環(huán)形單向鏈表的頭節(jié)點 head 和報數(shù) m.

返回：最后生存下來的節(jié)點，且這個節(jié)點自己組成環(huán)形單向鏈表，其他節(jié)點都刪除掉。

【難度】

士：★☆☆☆

【解答】

方法1：時間復雜度為 O( n * m)

這道題如果不考慮時間復雜度的話還是挺簡單的，就遍歷環(huán)形鏈表，每遍歷 m 個節(jié)點就刪除一個節(jié)點，知道鏈表只剩下一個節(jié)點就可以了。

代碼如下

 1    //時間復雜度為O(n*m)的解決方法
2    public static Node josephusKill(Node head, int m) {
3        if(head == null || m < 1)
4            return head;
5        Node last = head;
6        //定位到最后一個節(jié)點
7        while (head.next != last) {
8            head = head.next;
9        }
10        int count = 0;
11        while (head.next != head) {
12            if (++count == m) {
13                head.next = head.next.next;
14                count = 0;
15            } else {
16                head = head.next;
17            }
18        }
19        return head;
20    }

由于有些手機可能會出現(xiàn)亂碼問題，我這里再貼出圖片：

這個方法的時間復雜度為 O(n * m)。下面用時間復雜度為方法解決。

方法二：時間復雜度為 O(n)

這個方法的難度為：

校：★★★☆

我們可以給環(huán)形鏈表的節(jié)點編號，如果鏈表的節(jié)點數(shù)為 n, 則從頭節(jié)點開始，依次給節(jié)點編號，即頭節(jié)點為 1， 下一個節(jié)點為2， 最后一個節(jié)點為 n.

我們用 f(n) 表示當環(huán)形鏈表的長度為n時，生存下來的人的編號為 f(n)，顯然當 n = 1 時，f(n) = 1。假如我們能夠找出 f(n) 和 f(n-1) 之間的關(guān)系的話，我們我們就可以用遞歸的方式來解決了。我們假設 人員數(shù)為 n, 報數(shù)到 m 的人就自殺。則剛開始的編號為

…

m - 2

m - 1

m

m + 1

m + 2

…

進行了一次刪除之后，刪除了編號為m的節(jié)點。刪除之后，就只剩下 n - 1 個節(jié)點了，刪除前和刪除之后的編號轉(zhuǎn)換關(guān)系為：

刪除前     ---     刪除后

…          ---      …

m - 2     ---     n - 2

m - 1    ---      n - 1

m         ----    無(因為編號被刪除了)

m + 1     ---     1(因為下次就從這里報數(shù)了)

m + 2     ----     2

…         ----         …

新的環(huán)中只有 n - 1 個節(jié)點。且編號為 m + 1, m + 2, m + 3 的節(jié)點成了新環(huán)中編號為 1， 2， 3 的節(jié)點。

假設 old 為刪除之前的節(jié)點編號， new 為刪除了一個節(jié)點之后的編號，則 old 與 new 之間的關(guān)系為 old = (new + m - 1) % n + 1。

注：有些人可能會疑惑為什么不是 old = (new + m ) % n 呢？主要是因為編號是從 1 開始的，而不是從 0 開始的。如果 new + m == n的話，會導致最后的計算結(jié)果為 old = 0。所以 old = (new + m - 1) % n + 1.

這樣，我們就得出 f(n) 與 f(n - 1)之間的關(guān)系了，而 f(1) = 1.所以我們可以采用遞歸的方式來做。

代碼如下：

 1   //時間復雜度為O(n)
2    public static Node josephusKill2(Node head, int m) {
3        if(head == null || m < 1)
4            return head;
5        int n = 1;//統(tǒng)計一共有多少個節(jié)點
6        Node last = head;
7        while (last.next != head) {
8            n++;
9            last = last.next;
10        }
11        //直接用遞歸算出目的編號
12        int des = f(n, m);
13        //把目的節(jié)點取出來
14        while (--des != 0) {
15            head = head.next;
16        }
17        head.next = head;
18        return head;
19    }
20
21    private static int f(int n, int m) {
22        if (n == 1) {
23            return 1;
24        }
25        return (f(n - 1, m) + m - 1) % n + 1;
26    }

圖片代碼：

問題拓展

對于上道題，假設是從第 K 個節(jié)點開始報數(shù)刪除呢？ 又該如何解決呢？

當前題目：【鏈表問題】環(huán)形單鏈表約瑟夫問題-創(chuàng)新互聯(lián)
URL標題：http://weahome.cn/article/dgsoid.html