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

前言

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

站在用戶的角度思考問題，與客戶深入溝通，找到玉溪網(wǎng)站設(shè)計(jì)與玉溪網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站建設(shè)、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名申請(qǐng)、網(wǎng)站空間、企業(yè)郵箱。業(yè)務(wù)覆蓋玉溪地區(qū)。

【題目描述】

【要求】

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

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

【難度】

士：★☆☆☆

【解答】

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

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

代碼如下

 1    //時(shí)間復(fù)雜度為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        //定位到最后一個(gè)節(jié)點(diǎn)
 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    }

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

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

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

這個(gè)方法的難度為：

校：★★★☆

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

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

…

m - 2

m - 1

m

m + 1

m + 2

…

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

刪除前     ---     刪除后

…          ---      …

m - 2     ---     n - 2

m - 1    ---      n - 1

m         ----    無(因?yàn)榫幪?hào)被刪除了)

m + 1     ---     1(因?yàn)橄麓尉蛷倪@里報(bào)數(shù)了)

m + 2     ----     2

…         ----         …

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

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

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

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

代碼如下：

 1   //時(shí)間復(fù)雜度為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)計(jì)一共有多少個(gè)節(jié)點(diǎn)
 6        Node last = head;
 7        while (last.next != head) {
 8            n++;
 9            last = last.next;
10        }
11        //直接用遞歸算出目的編號(hào)
12        int des = f(n, m);
13        //把目的節(jié)點(diǎn)取出來
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    }

圖片代碼：

問題拓展

對(duì)于上道題，假設(shè)是從第 K 個(gè)節(jié)點(diǎn)開始報(bào)數(shù)刪除呢？ 又該如何解決呢？