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

emacsnw

我同學(xué)最近面試某IT公司的電話面試一個(gè)題目，他說(shuō)當(dāng)時(shí)可能回答的不好，和我討論了一下。這里來(lái)問(wèn)問(wèn)大家。

給你一個(gè)單向鏈表的頭指針，可能最后不是NULL終止，而是循環(huán)鏈表。題目問(wèn)你怎么找出這個(gè)鏈表循環(huán)部分的第一個(gè)節(jié)點(diǎn)。比如下面的鏈表：

1. 
   
2. 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循環(huán)
   

復(fù)制代碼

就應(yīng)該返回結(jié)點(diǎn)3的位置。

當(dāng)然盡量用少的空間和時(shí)間是題目的要求。

cjaizss

兩個(gè)指針，一個(gè)步長(zhǎng)為1，一個(gè)步長(zhǎng)為2，往前進(jìn)，時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(1)

converse

原帖由 cjaizss 于 2007-2-5 14:17 發(fā)表
兩個(gè)指針，一個(gè)步長(zhǎng)為1，一個(gè)步長(zhǎng)為2，往前進(jìn)，時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(1)

這個(gè)題目和原來(lái)的判斷鏈表是不是循環(huán)鏈表的問(wèn)題有一些區(qū)別的,原來(lái)是要證明鏈表是不是循環(huán)的,現(xiàn)在的是已知某部分是循環(huán)的要求找到這個(gè)循環(huán)的頭結(jié)點(diǎn).

我想到的辦法是,從頭開(kāi)始一次取出把鏈表中的結(jié)點(diǎn)組成另一個(gè)鏈表,判斷這個(gè)鏈表是不是循環(huán)的,第一個(gè)滿足條件的頭結(jié)點(diǎn)就是了.

比如以上面的測(cè)試數(shù)據(jù)為例:
第一次取出:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)
第二次取出:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)
第三次取出:
2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3)

以此類推.

不知道有沒(méi)有更好的辦法,關(guān)注.

boxpei

所有節(jié)點(diǎn)排序，第一個(gè)重復(fù)出現(xiàn)的節(jié)點(diǎn)就是，拋磚引玉。

cjaizss

原帖由 converse 于 2007-2-5 14:23 發(fā)表


這個(gè)題目和原來(lái)的判斷鏈表是不是循環(huán)鏈表的問(wèn)題有一些區(qū)別的,原來(lái)是要證明鏈表是不是循環(huán)的,現(xiàn)在的是已知某部分是循環(huán)的要求找到這個(gè)循環(huán)的頭結(jié)點(diǎn).

我想到的辦法是,從頭開(kāi)始一次取出把鏈表中的結(jié)點(diǎn)組成另一 ...

恩，剛才沒(méi)細(xì)想，現(xiàn)在想想確實(shí)是那么回事情。
空間復(fù)雜度O(n),時(shí)間復(fù)雜度O(n^2)
構(gòu)造一個(gè)長(zhǎng)度為O(n)的buffer,折半查找插入排序
無(wú)論是空間復(fù)雜度，還是時(shí)間復(fù)雜度，這已經(jīng)是極限。
級(jí)別無(wú)法提高，但是或許可以找到同一級(jí)別上更快的算法。

Edengundam

原帖由 converse 于 2007-2-5 14:23 發(fā)表


這個(gè)題目和原來(lái)的判斷鏈表是不是循環(huán)鏈表的問(wèn)題有一些區(qū)別的,原來(lái)是要證明鏈表是不是循環(huán)的,現(xiàn)在的是已知某部分是循環(huán)的要求找到這個(gè)循環(huán)的頭結(jié)點(diǎn).

我想到的辦法是,從頭開(kāi)始一次取出把鏈表中的結(jié)點(diǎn)組成另一 ...

和我想得大致一樣...但是復(fù)雜度O(n^2)

Edengundam

原帖由 boxpei 于 2007-2-5 14:30 發(fā)表
所有節(jié)點(diǎn)排序，第一個(gè)重復(fù)出現(xiàn)的節(jié)點(diǎn)就是，拋磚引玉。

這個(gè)應(yīng)該是O(nlogn)了...主要開(kāi)銷是對(duì)指針地址排序...

這個(gè)我說(shuō)錯(cuò)了...取所有節(jié)點(diǎn)地址的開(kāi)銷貌似..

[ 本帖最后由 Edengundam 于 2007-2-5 15:12 編輯 ]

bleem1998

原帖由 cjaizss 于 2007-2-5 14:17 發(fā)表
兩個(gè)指針，一個(gè)步長(zhǎng)為1，一個(gè)步長(zhǎng)為2，往前進(jìn)，時(shí)間復(fù)雜度O(n),空間復(fù)雜度O(1)

我的基于這個(gè)算法
首先確認(rèn)是否存在循環(huán)
如果存在循環(huán)
那么最后兩個(gè)指針相會(huì)的地方一定是在循環(huán)的圈圈里
如果對(duì)這個(gè)節(jié)點(diǎn)不斷的做next的話
會(huì)出現(xiàn)死循環(huán)
OK
這個(gè)時(shí)候再?gòu)逆湵眍^頭上開(kāi)始
把每個(gè)節(jié)點(diǎn)都判斷一下是否在那個(gè)循環(huán)的圈圈里


這個(gè)算法不的內(nèi)存消耗率為0
咩哈哈哈

lishengxu

不太明白converse的算法，希望斑竹給解釋一下唄~
你第一次取出了第一個(gè)節(jié)點(diǎn)，但是你只知道頭節(jié)點(diǎn)，不知道尾節(jié)點(diǎn)和鏈表的長(zhǎng)度��？
你怎么能判斷出什么時(shí)候第一次結(jié)束啊？
我覺(jué)得最好是能夠給訪問(wèn)過(guò)的節(jié)點(diǎn)做上已經(jīng)訪問(wèn)的標(biāo)志，這樣不就好辦了么！

converse

原帖由 lishengxu 于 2007-2-5 14:44 發(fā)表
不太明白converse的算法，希望斑竹給解釋一下唄~
你第一次取出了第一個(gè)節(jié)點(diǎn)，但是你只知道頭節(jié)點(diǎn)，不知道尾節(jié)點(diǎn)和鏈表的長(zhǎng)度��？
你怎么能判斷出什么時(shí)候第一次結(jié)束啊？
我覺(jué)得最好是能夠給訪問(wèn)過(guò)的節(jié)點(diǎn)做上已 ...

是啊,不知道哪里結(jié)束是個(gè)問(wèn)題,我馬虎了.