前言

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

【題目描述】

【要求】

輸入：一個環形單向鏈表的頭節點 head 和報數 m.

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

【難度】

士：★☆☆☆

【解答】

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

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

代碼如下

 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        //定位到最后一個節點
 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    }

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

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

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

這個方法的難度為：

校：★★★☆

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

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

…

m - 2

m - 1

m

m + 1

m + 2

…

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

刪除前     ---     刪除后

…          ---      …

m - 2     ---     n - 2

m - 1    ---      n - 1

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

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

m + 2     ----     2

…         ----         …

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

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

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

這樣，我們就得出 f(n) 與 f(n - 1)之間的關系了，而 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;//統計一共有多少個節點
 6        Node last = head;
 7        while (last.next != head) {
 8            n++;
 9            last = last.next;
10        }
11        //直接用遞歸算出目的編號
12        int des = f(n, m);
13        //把目的節點取出來
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 個節點開始報數刪除呢？ 又該如何解決呢？