亚洲av成人无遮挡网站在线观看,少妇性bbb搡bbb爽爽爽,亚洲av日韩精品久久久久久,兔费看少妇性l交大片免费,无码少妇一区二区三区

  免費注冊 查看新帖 |

Chinaunix

  平臺 論壇 博客 文庫
最近訪問板塊 發(fā)新帖
查看: 50214 | 回復(fù): 115
打印 上一主題 下一主題

一個關(guān)于單向鏈表的面試題。 [復(fù)制鏈接]

論壇徽章:
0
跳轉(zhuǎn)到指定樓層
1 [收藏(0)] [報告]
發(fā)表于 2007-02-05 14:11 |只看該作者 |倒序瀏覽
我同學(xué)最近面試某IT公司的電話面試一個題目,他說當(dāng)時可能回答的不好,和我討論了一下。這里來問問大家。

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


  1. 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> (3) 循環(huán)
復(fù)制代碼


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

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

論壇徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11數(shù)據(jù)庫技術(shù)版塊每日發(fā)帖之星
日期:2016-08-03 06:20:00數(shù)據(jù)庫技術(shù)版塊每日發(fā)帖之星
日期:2016-08-04 06:20:00
2 [報告]
發(fā)表于 2007-02-05 14:17 |只看該作者
兩個指針,一個步長為1,一個步長為2,往前進,時間復(fù)雜度O(n),空間復(fù)雜度O(1)

論壇徽章:
0
3 [報告]
發(fā)表于 2007-02-05 14:23 |只看該作者
原帖由 cjaizss 于 2007-2-5 14:17 發(fā)表
兩個指針,一個步長為1,一個步長為2,往前進,時間復(fù)雜度O(n),空間復(fù)雜度O(1)


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

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

比如以上面的測試數(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)

以此類推.

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

論壇徽章:
0
4 [報告]
發(fā)表于 2007-02-05 14:30 |只看該作者
所有節(jié)點排序,第一個重復(fù)出現(xiàn)的節(jié)點就是,拋磚引玉。

論壇徽章:
3
2015年迎新春徽章
日期:2015-03-04 09:56:11數(shù)據(jù)庫技術(shù)版塊每日發(fā)帖之星
日期:2016-08-03 06:20:00數(shù)據(jù)庫技術(shù)版塊每日發(fā)帖之星
日期:2016-08-04 06:20:00
5 [報告]
發(fā)表于 2007-02-05 14:34 |只看該作者
原帖由 converse 于 2007-2-5 14:23 發(fā)表


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

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

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

論壇徽章:
0
6 [報告]
發(fā)表于 2007-02-05 14:38 |只看該作者
原帖由 converse 于 2007-2-5 14:23 發(fā)表


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

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



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

論壇徽章:
0
7 [報告]
發(fā)表于 2007-02-05 14:41 |只看該作者
原帖由 boxpei 于 2007-2-5 14:30 發(fā)表
所有節(jié)點排序,第一個重復(fù)出現(xiàn)的節(jié)點就是,拋磚引玉。



這個應(yīng)該是O(nlogn)了...主要開銷是對指針地址排序...

這個我說錯了...取所有節(jié)點地址的開銷貌似..

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

論壇徽章:
0
8 [報告]
發(fā)表于 2007-02-05 14:42 |只看該作者
原帖由 cjaizss 于 2007-2-5 14:17 發(fā)表
兩個指針,一個步長為1,一個步長為2,往前進,時間復(fù)雜度O(n),空間復(fù)雜度O(1)


我的基于這個算法
首先確認(rèn)是否存在循環(huán)
如果存在循環(huán)
那么最后兩個指針相會的地方一定是在循環(huán)的圈圈里
如果對這個節(jié)點不斷的做next的話
會出現(xiàn)死循環(huán)
OK
這個時候再從鏈表頭頭上開始
把每個節(jié)點都判斷一下是否在那個循環(huán)的圈圈里


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

論壇徽章:
0
9 [報告]
發(fā)表于 2007-02-05 14:44 |只看該作者
不太明白converse的算法,希望斑竹給解釋一下唄~
你第一次取出了第一個節(jié)點,但是你只知道頭節(jié)點,不知道尾節(jié)點和鏈表的長度啊?
你怎么能判斷出什么時候第一次結(jié)束啊?
我覺得最好是能夠給訪問過的節(jié)點做上已經(jīng)訪問的標(biāo)志,這樣不就好辦了么!

論壇徽章:
0
10 [報告]
發(fā)表于 2007-02-05 14:51 |只看該作者
原帖由 lishengxu 于 2007-2-5 14:44 發(fā)表
不太明白converse的算法,希望斑竹給解釋一下唄~
你第一次取出了第一個節(jié)點,但是你只知道頭節(jié)點,不知道尾節(jié)點和鏈表的長度?
你怎么能判斷出什么時候第一次結(jié)束?
我覺得最好是能夠給訪問過的節(jié)點做上已 ...


是啊,不知道哪里結(jié)束是個問題,我馬虎了.
您需要登錄后才可以回帖 登錄 | 注冊

本版積分規(guī)則 發(fā)表回復(fù)

  

北京盛拓優(yōu)訊信息技術(shù)有限公司. 版權(quán)所有 京ICP備16024965號-6 北京市公安局海淀分局網(wǎng)監(jiān)中心備案編號:11010802020122 niuxiaotong@pcpop.com 17352615567
未成年舉報專區(qū)
中國互聯(lián)網(wǎng)協(xié)會會員  聯(lián)系我們:huangweiwei@itpub.net
感謝所有關(guān)心和支持過ChinaUnix的朋友們 轉(zhuǎn)載本站內(nèi)容請注明原作者名及出處

清除 Cookies - ChinaUnix - Archiver - WAP - TOP