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

emacsnw

原帖由 cjaizss 于 2007-2-5 00:07 发表

O(1)空间复杂度是不存在的，信息量不够。

刚开始我也这样想的，但是想到两个额外指针可以判断链表是否有循环，这里至少有些类似。
呵呵，当然是否存在这样的算法可能只有面试官知道了。

1jjk

要不让那哥们找一下那个出题的哥们
然后给个答案，然后学习学习吧

boxpei

hash本身的时间空间复杂度也要考虑吧。

cjaizss

哦，存在空间复杂度O(1),时间复杂度O(n^2)的算法，利用原链表的存储空间。是种很朴素的算法，对于不可预知链表长度而言并不低效。
可预知长度的话，选择O(1)空间还要选择O(n)时间是不可行的。

bleem1998

写了段python代码
验证了刚才的算法
没有复制任何数据
只是指针指来指去

1. 
   
2. #!/usr/bin/env python
   
3. 
   
4. nd7 = [1, None, 'nd7']
   
5. nd6 = [1, nd7, 'nd6']
   
6. nd5 = [1, nd6, 'nd5']
   
7. nd4 = [1, nd5, 'nd4']
   
8. nd3 = [1, nd4, 'nd3']
   
9. nd2 = [1, nd3, 'nd2']
   
10. head = nd1 = [1, nd2, 'nd1']
    
11. nd7[1] = nd3        #recycle
    
12. 
    
13. def get_next(node):
    
14.         if node != None:
    
15.                 return node[1]
    
16.         else:
    
17.                 return None
    
18. 
    
19. def has_cycle(head):
    
20.         p1 = head
    
21.         p2 = head
    
22.         while (p1 != None) and (p2 != None):
    
23.                 p1 = get_next(p1)
    
24.                 p2 = get_next(p2)
    
25.                 p2 = get_next(p2)
    
26.                 if p1 == None or p2 == None:
    
27.                         return [0, None]
    
28.                 if id(p1) == id(p2):
    
29.                         return [1, p1]
    
30.         return [0, None]
    
31. 
    
32. def node_in_cycle(node, cycle_nd):
    
33.         bak = cycle_nd
    
34.         while True:
    
35.                 if id(node) == id(cycle_nd):
    
36.                         return True
    
37.                 cycle_nd = get_next(cycle_nd)
    
38.                 if id(bak) == id(cycle_nd):
    
39.                         return False
    
40. 
    
41. def look_for_cycle_point(head, cycle_nd):
    
42.         while head != None:
    
43.                 if node_in_cycle(head, cycle_nd):
    
44.                         return head
    
45.                 else:
    
46.                         head = get_next(head)
    
47.         return None
    
48. 
    
49. if __name__ == '__main__':
    
50.         print 'Go...'
    
51.         ret = has_cycle(head)
    
52.         if ret[0]:
    
53.                 node = look_for_cycle_point(head,ret[1])
    
54.                 print node[2]
    
55.         else:
    
56.                 print 'No cycle'
    

复制代码

skipjack

1. 
   
2. 时间复杂度O(n),空间复杂度O(n/8) ,引用计数大于1即是交结点。不知我这么说，多少人可以明白
   

复制代码

[ 本帖最后由 skipjack 于 2007-2-5 17:12 编辑 ]

softsongs

无知无谓啊～

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

softsongs

做个标记，晚上听完音乐会回来解答，
基本上是把数组看成一颗树，对其进行深度遍历，刚开始每个节点mark为白色，遍历一次mark为灰色，回退过的几点编程白色。经历两次即为我们要找的节点。

cjaizss

原帖由 softsongs 于 2007-2-5 17:41 发表
无知无谓啊～

...
我的错。
在链表长度不可预知的情况下，也依然存在空间复杂度O(n),时间复杂度O(nlogn)的算法。
构造sort-tree存储信息。
时间复杂度算错了

独孤九贱

觉得这题，就像字符串中查找子串……