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

1jjk

我想
他的意思應(yīng)該是
去掉非循環(huán)鏈表的節(jié)點，例如去掉節(jié)點到第8個時，正好形成了一個環(huán)，這個時候環(huán)的第一個節(jié)點算是8了，是了？

DraculaW

設(shè)個一樣長的hash 以地址為index 是否訪問為key
當(dāng)?shù)谝粋�index的key是被設(shè)置了的 那么就是 要找的那個了
呵呵
這個應(yīng)該時間是o(n) 空間應(yīng)該是o(n)吧  看hash值的選擇了

converse

原帖由 1jjk 于 2007-2-5 14:55 發(fā)表
我想
他的意思應(yīng)該是
去掉非循環(huán)鏈表的節(jié)點，例如去掉節(jié)點到第8個時，正好形成了一個環(huán)，這個時候環(huán)的第一個節(jié)點算是8了，是了？

最初是這個想法,但是前面的朋友已經(jīng)說了不知道鏈表在哪里結(jié)束,是個麻煩的事情唉~~

cjaizss

平均
空間復(fù)雜度O(n),時間復(fù)雜度O(n^2)，這是不可超越的。
只可以在這一級別上提高。

1jjk

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


最初是這個想法,但是前面的朋友已經(jīng)說了不知道鏈表在哪里結(jié)束,是個麻煩的事情唉~~

是的
不能結(jié)束
可以用鏈表里面的data域判斷嗎？
例如第一個節(jié)點的data域為1，遞加，然后到環(huán)的時候，環(huán)肯定得有第一個域和最后一個域相接啊
不過這樣的話就要多申請點空間了

emacsnw

原帖由 cjaizss 于 2007-2-4 23:04 發(fā)表
平均
空間復(fù)雜度O(n),時間復(fù)雜度O(n^2)，這是不可超越的。
只可以在這一級別上提高。

為什么是這個結(jié)論？呵呵。

lishengxu

這句話什么意思
我沒看懂
第一個節(jié)點的data域為1，遞加，然后到環(huán)的時候，環(huán)肯定得有第一個域和最后一個域相接啊
1jjk能解釋一下么？

cjaizss

原帖由 emacsnw 于 2007-2-5 15:07 發(fā)表


為什么是這個結(jié)論？呵呵。

可以證明的。
這是對于鏈表元素個數(shù)事先不可知而言的。
如果事先鏈表元素個數(shù)大致知道，則存在
空間復(fù)雜度O(n),時間復(fù)雜度O(n)

1jjk

原帖由 lishengxu 于 2007-2-5 15:21 發(fā)表
這句話什么意思
我沒看懂
第一個節(jié)點的data域為1，遞加，然后到環(huán)的時候，環(huán)肯定得有第一個域和最后一個域相接啊
1jjk能解釋一下么？

struct pointer{
int data;
struct pointer * next;
}


每個節(jié)點多一個int data;
當(dāng)讀一個next的時候data加一，然后這個data與下一個的data進行比較

也不知道這么做可以不可以
我的思路是這樣的，電腦掛了，要不就在家好好的實驗一下，呵呵
現(xiàn)在在網(wǎng)吧呢

langue

--

大家討論的氣氛很好，繼續(xù)……

--