一個關(guān)于單向鏈表的面試題。

ArXoR

原帖由 emacsnw 于 2/6/07 04:27 發(fā)表
想了一下，似乎下面的算法可以：O(1)空間，O(n)時間。
兩個額外指針p1, p2，開始都指向頭S。設(shè)需要找到的循環(huán)部分第一個結(jié)點的位置為A，S到A的距離為x (x可能為0），鏈表的循環(huán)部分長度為y (y > 0)。

算法 ...

方法是對的, 問題有點點

z應(yīng)該是p1從A到在B和p2相遇所走過的路程, 才能用那個方程

emacsnw

原帖由 ArXoR 于 2007-2-5 22:38 發(fā)表


方法是對的, 問題有點點

z應(yīng)該是p1從A到在B和p2相遇所走過的路程, 才能用那個方程

p1應(yīng)該是可以保證沒有走完這個環(huán)的。

gaosen2463

不能保證吧
如果環(huán)特別小呢

gaosen2463

是我想錯了
p1是不能走完哪個環(huán)

ArXoR

原帖由 emacsnw 于 2/6/07 16:30 發(fā)表


p1應(yīng)該是可以保證沒有走完這個環(huán)的。

是可以證明z<=y, 但是敘述上應(yīng)該嚴謹... ^_^

sdbook

算出循環(huán)鏈的長度，總長度－循環(huán)鏈長度。

tuzhiwei123

訪問的接點做個標(biāo)記，如果發(fā)現(xiàn)在訪問后面的節(jié)點出現(xiàn)標(biāo)記，就知道從什么地方循環(huán)了

dixin01

許多人犯了一個嚴重的錯誤，在不知道鏈表的確切個數(shù)的情況下，
是無法進行循環(huán)或遞歸的操作的，這樣去求逆轉(zhuǎn)鏈表或摘取節(jié)點，
會因為無法確定循環(huán)的結(jié)束條件，從而陷入死循環(huán)！

以下是我的解答：

struct node* find_cycleNode(struct node *list_x)
{
     struct node *p0, *p1;
     if (list_x==list_x->next)
        return(list_x);
     p1=list_x->next;
     while (1)  {
        for(p0=list_x; p0!=p1; p0=p0->next)
           if (p0==p1->next)
              return(p0);
        p1=p1->next;
     }
}

算法的時間復(fù)雜度：O(n^2),  空間復(fù)雜度：O(1)

[ 本帖最后由 dixin01 于 2007-4-28 00:11 編輯 ]

emacsnw

原帖由 dixin01 于 2007-4-27 06:28 發(fā)表
許多人犯了一個嚴重的錯誤，在不知道鏈表的確切個數(shù)的情況下，
是無法進行循環(huán)或遞歸的操作的，這樣去求逆轉(zhuǎn)鏈表或摘取節(jié)點，
會因為無法確定循環(huán)的結(jié)束條件，從而陷入死循環(huán)！

以下是我的解答：

struct  ...

兩個步進不一樣(1和2)的指針相等了就中止，怎么會死循環(huán)。

dixin01

原帖由 emacsnw 于 2007-4-28 02:24 發(fā)表

兩個步進不一樣(1和2)的指針相等了就中止，怎么會死循環(huán)。

你的算法是正確的，比我的效率高，時間復(fù)雜度為O(n)，我說的是其他人的。