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

win_hate

設(shè)非循環(huán)部分有 a 個(gè)點(diǎn)， 循環(huán)部分有 b 個(gè)點(diǎn)

用大步小步法，小步步幅為 1， 大步步幅為 2，經(jīng)過 i 步后重合。從重合點(diǎn)出發(fā)，搜索自身并記數(shù)，可以得到 b.

令 q = [(i-1)/b]

用兩個(gè)指針，一個(gè)從 qb +1 點(diǎn)出發(fā)，一個(gè)從重合點(diǎn)出發(fā)，步幅為1，直到重合，經(jīng)過的步數(shù)就是 r. 而 a=bq+r.

[ 本帖最后由 win_hate 于 2007-2-5 21:01 編輯 ]

azhoulinux

是否可以這樣考慮：
單鏈表每一個(gè)節(jié)點(diǎn)其指向下一個(gè)節(jié)點(diǎn)的指針都是不同的，這道題在于會(huì)出現(xiàn)
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循環(huán)
2節(jié)點(diǎn)與8節(jié)點(diǎn)都是指向3節(jié)點(diǎn)，引入一個(gè)新的棧，存儲(chǔ)每個(gè)節(jié)點(diǎn)指針的值，一旦出現(xiàn)相同的指針值，那么就可以說出現(xiàn)了循環(huán)，比如2節(jié)點(diǎn)與8節(jié)點(diǎn)都是指向3節(jié)點(diǎn).

你們看看行不行？

Edengundam

O(1)復(fù)雜度...意思是常量, 不隨著實(shí)例規(guī)模的變化而變化. 一萬個(gè)指針, 都應(yīng)該記為O(1)...呵呵


O(n/應(yīng)該表示為O(n)的復(fù)雜度...

zjw12112

構(gòu)造hash表，我覺得時(shí)間復(fù)雜度是0(nlog2^n)吧？不好意思，忘了hash的時(shí)間復(fù)雜度。
想出了一個(gè)空間復(fù)雜度為0(n),時(shí)間復(fù)雜度也為0(n)的算法，不知道是否可行，大家看一看。
首先根據(jù)鏈表創(chuàng)建一個(gè)逆序的鏈表。如下：
原始：1->2->3->4->5->6->7->8->(3)
逆序：1->2->3->8->7->6->5->4->(3)
赫赫，接下來就很容易判斷了，分別從兩個(gè)鏈表頭指針開始，找到next指針不一樣的那個(gè)節(jié)點(diǎn)就是最終目標(biāo)了。

12013396

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

標(biāo)準(zhǔn)答案!!

Edengundam

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

恩...明白這個(gè)算法的意思...偶太弱了..這算法1967年就有了...

emacsnw

想了一下，似乎下面的算法可以：O(1)空間，O(n)時(shí)間。
兩個(gè)額外指針p1, p2，開始都指向頭S。設(shè)需要找到的循環(huán)部分第一個(gè)結(jié)點(diǎn)的位置為A，S到A的距離為x (x可能為0），鏈表的循環(huán)部分長度為y (y > 0)。

算法開始和判斷循環(huán)的方法一樣：令p1每次走一步，p2每次走兩步，我們知道，如果鏈表有環(huán)，最后p1和p2一定在環(huán)上某個(gè)地方B相遇，我們?cè)O(shè)A-B之間的距離為z (z可能為0)。

很顯然，p1走了x+z步，那么p2走了2(x+z)步，由于p1和p2在這么多步后相遇，因此有2(x+z) - (x+z) = K*y (K > 0的整數(shù))，因此我們有x+z = K*y。

假如我們能讓p1在B點(diǎn)開始繼續(xù)往前走x步的話，它一定會(huì)走到A，因?yàn)閦+x是y的倍數(shù)。有人會(huì)說，費(fèi)話如果知道x的話，我只要讓p2從起點(diǎn)S開始往前走x步，不就也能走到A嗎？其實(shí)解法就是這么簡單，讓p1在剛剛相遇的地方B繼續(xù)一次走一步，而p2從起點(diǎn)S開始一次走一步，那么它們第一次相遇的地方一定是A，并且正好經(jīng)過了x步（當(dāng)然你不需要計(jì)數(shù)）。

這就是算法。還是比如下面的例子：0->1->2->3->4->5->6->7->8->(3)
剛開始p1, p2都在0，p1一次走一步，p2一次走兩步，它們最終會(huì)在結(jié)點(diǎn)6相遇。這時(shí)候讓p1繼續(xù)從6開始往前走，而p2從0開始也一次往前走1步，那么我么就會(huì)發(fā)現(xiàn)它們會(huì)相遇在3，返回這個(gè)地址就是所需要的解。

lishengxu

老兄你的算法不對(duì)阿2(x+z) - (x+z) = K*y
這等式有問題阿!!!!
因該是2(x+n*z)-(x+m*z) = k*y

[ 本帖最后由 lishengxu 于 2007-2-6 09:26 編輯 ]

emacsnw

原帖由 lishengxu 于 2007-2-5 17:23 發(fā)表
老兄你的算法不對(duì)阿2(x+z) - (x+z) = K*y
這等式有問題阿!!!!
因該是2(x+n*z)-(x+m*z) = k*y

p2比p1多走了環(huán)長的整數(shù)倍，有什么問題嗎？

skipjack

原帖由 Edengundam 于 2007-2-5 20:32 發(fā)表
O(1)復(fù)雜度...意思是常量, 不隨著實(shí)例規(guī)模的變化而變化. 一萬個(gè)指針, 都應(yīng)該記為O(1)...呵呵


O(n/應(yīng)該表示為O(n)的復(fù)雜度...

哦～，我是想用O(n/強(qiáng)調(diào)空間復(fù)雜度為O(0)（可能就是你們常說的O(1)吧，沒系統(tǒng)學(xué)習(xí)過算法，不會(huì)專業(yè)表達(dá)，但我感覺這題也不需要什么算法），gcc結(jié)構(gòu)體4字節(jié)對(duì)齊時(shí)剩下的空間，以及結(jié)構(gòu)體成員變量只要能擠出1個(gè)bit用于計(jì)數(shù)，就足夠了。比什么大步、小步、二叉、折半，效率高多了。