環(huán)形單鏈表約瑟夫問題

印度阿三17 2019-02-24

展開全文

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

【題目描述】

【要求】

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

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

【難度】

士：★☆☆☆

【解答】

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

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

代碼如下

    //時間復(fù)雜度為O(n*m)的解決方法
    public static Node josephusKill(Node head, int m) {
        if(head == null || m < 1)
            return head;
        Node last = head;
        //定位到最后一個節(jié)點
        while (head.next != last) {
            head = head.next;
        }
        System.out.println(head.value);
        int count = 0;
        while (head.next != head) {
            if (  count == m) {
                head.next = head.next.next;
                count = 0;
            } else {
                head = head.next;
            }
        }
        return head;
    }

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

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

這個方法的難度為：

校：★★★☆

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

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

...

m - 2

m - 1

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é)點。

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

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

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

代碼如下：

   //時間復(fù)雜度為O(n)
    public static Node josephusKill2(Node head, int m) {
        if(head == null || m < 1)
            return head;
        int n = 1;//統(tǒng)計一共有多少個節(jié)點
        Node last = head;
        while (last.next != head) {
            n  ;
            last = last.next;
        }
        //直接用遞歸算出目的編號
        int des = f(n, m);
        //把目的節(jié)點取出來
        while (--des != 0) {
            head = head.next;
        }
        head.next = head;
        return head;
    }

    private static int f(int n, int m) {
        if (n == 1) {
            return 1;
        }
        return (getDes(n - 1, m)   m - 1) % n   1;
    }