一个关于单向链表的面试题。

1jjk

我想
他的意思应该是
去掉非循环链表的节点，例如去掉节点到第8个时，正好形成了一个环，这个时候环的第一个节点算是8了，是了？

DraculaW

设个一样长的hash 以地址为index 是否访问为key
当第一个index的key是被设置了的 那么就是 要找的那个了
呵呵
这个应该时间是o(n) 空间应该是o(n)吧  看hash值的选择了

converse

原帖由 1jjk 于 2007-2-5 14:55 发表
我想
他的意思应该是
去掉非循环链表的节点，例如去掉节点到第8个时，正好形成了一个环，这个时候环的第一个节点算是8了，是了？

最初是这个想法,但是前面的朋友已经说了不知道链表在哪里结束,是个麻烦的事情唉~~

cjaizss

平均
空间复杂度O(n),时间复杂度O(n^2)，这是不可超越的。
只可以在这一级别上提高。

1jjk

原帖由 converse 于 2007-2-5 14:59 发表


最初是这个想法,但是前面的朋友已经说了不知道链表在哪里结束,是个麻烦的事情唉~~

是的
不能结束
可以用链表里面的data域判断吗？
例如第一个节点的data域为1，递加，然后到环的时候，环肯定得有第一个域和最后一个域相接啊
不过这样的话就要多申请点空间了

emacsnw

原帖由 cjaizss 于 2007-2-4 23:04 发表
平均
空间复杂度O(n),时间复杂度O(n^2)，这是不可超越的。
只可以在这一级别上提高。

为什么是这个结论？呵呵。

lishengxu

这句话什么意思
我没看懂
第一个节点的data域为1，递加，然后到环的时候，环肯定得有第一个域和最后一个域相接啊
1jjk能解释一下么？

cjaizss

原帖由 emacsnw 于 2007-2-5 15:07 发表


为什么是这个结论？呵呵。

可以证明的。
这是对于链表元素个数事先不可知而言的。
如果事先链表元素个数大致知道，则存在
空间复杂度O(n),时间复杂度O(n)

1jjk

原帖由 lishengxu 于 2007-2-5 15:21 发表
这句话什么意思
我没看懂
第一个节点的data域为1，递加，然后到环的时候，环肯定得有第一个域和最后一个域相接啊
1jjk能解释一下么？

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


每个节点多一个int data;
当读一个next的时候data加一，然后这个data与下一个的data进行比较

也不知道这么做可以不可以
我的思路是这样的，电脑挂了，要不就在家好好的实验一下，呵呵
现在在网吧呢

langue

--

大家讨论的气氛很好，继续……

--