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

softsongs

把链表看成一个有向图，深度优先遍历该有向图，判断有无循环出现。
懒得再用中文写一遍具体算法了，看下面的代码实现吧，英文注释解释的很清楚了。

时间复杂度 O(e), 链表边的总数。
空间复杂度 O(1).
有向图采用邻接表实现。

1. 
   
2. /* file: DFSDetectLoop.cpp */
   
3. /*
   
4. *  Detect if the graph has loop -- For both Undigraph and digraph
   
5. *  Complexity: O(e); e is the number of arcs in Graph.
   
6. *   
   
7. *  BUG Reported:
   
8. *  1. Apr-26-07
   
9. *     Not support Undigraph yet ! Fix me !!!
   
10. *     - Fixed on Apr-26-08.
    
11. *  
    
12. *  Return
    
13. *  1 - Loop detected.
    
14. *  0 - No loop detected.     
    
15. *  *
    
16. *  Algrithm:
    
17. *  1. Init all the nodes color to WHITE.
    
18. *  2. DFS graph
    
19. *      For each the nodes v in graph, do step (1) and (2).
    
20. *      (1) If v is WHITE, DFS from node v:
    
21. *          (a) Mark v as GRAY.   
    
22. *          (b) For every nodes tv adjacent with node v,
    
23. *              (i)   If the current visiting node is gray, then loop detected. exit.
    
24. *              (ii)  Goto Step (1).
    
25. *              (iii) All the nodes on sub-tree of tv have been visited. Mark node tv as BLACK.
    
26. *       (2) All the nodes on sub-tree of v have been visited. Mark node v as BLACK.
    
27. *      
    
28. * Function DFSDetectLoop is valid for both Undigraph and digraph.
    
29. *
    
30. * */
    
31. int DFSDetectLoop (ALGraph *graph, int VisitFunc (ALGraph *graph, int v))
    
32. {
    
33.     int v;
    
34. 
    
35.     for (v = 0; v < graph->vexnum; v++)
    
36.     {   
    
37.         MarkNodeColor (graph, v, WHITE);
    
38.     }
    
39.     for (v = 0; v < graph->vexnum; v++)
    
40.     {   
    
41.         if (graph->vertices[v].color == WHITE)
    
42.         {   
    
43.             /* We are good to call DFSDetectLoopSub the first
    
44.              * time with pv = -1, because no node equals -1.
    
45.              * */
    
46.             if (1 == DFSDetectLoopSub (graph, v, -1, VisitFunc))
    
47.                 return 1;
    
48.         }
    
49.         MarkNodeColor (graph, v, BLACK);
    
50.     }
    
51.     return 1;
    
52. }
    
53. 
    
54. /*         
    
55. * Start from node v, DFS graph to detect loop.
    
56. *  pv is the node that just visited v. pv is used to avoid v to visit pv again.
    
57. *  pv is introduced to support Undigraph.
    
58. *  
    
59. * NOTE:
    
60. *      Before calling DFSDetectLoopSub, make sure node v is not visited yet.
    
61. * */
    
62. int DFSDetectLoopSub (ALGraph *graph, int v, int pv, int VisitFunc (ALGraph *graph, int v))
    
63. {
    
64.    assert (graph->vertices[v].color == WHITE);
    
65. 
    
66.    MarkNodeColor (graph, v, GRAY);
    
67. 
    
68.    VisitFunc (graph, v);
    
69. 
    
70.    ArcNode *arc;
    
71.    arc = graph->vertices[v].firstarc;
    
72.    while (arc)
    
73.    {
    
74.         int tv = arc->adjvex;
    
75. 
    
76.         /* For Undigraph, if tv equals pv, this arc should not be count.
    
77.          * Because we have just visited from pv to v.
    
78.          * Just go ahead to check next vertex connected with v.
    
79.          * 1----2, after visit 1, we will visit 2, while visiting 2, 1 will be the 1st node visited.
    
80.          *
    
81.          * For digraph, we need to check loop even tv equals pv.
    
82.          * Because there is case that node v points to u, and u points to v.
    
83.          * */
    
84.         if ((graph->kind == AG) && (tv != pv))
    
85.         {
    
86.             if ( graph->vertices[tv].color == GRAY )
    
87.             {
    
88.                 cout << "Gray node visited at node: " << tv + 1 <<endl;
    
89.                 cout << "DFSDetectLoopSub: Loop Detected at from node " << v + 1<<" to "<< tv + 1 <<" !" <<endl;
    
90.                 return 1;
    
91.             }
    
92. 
    
93.             if (graph->vertices[tv].color == WHITE)
    
94.             {
    
95.                 if (1 == DFSDetectLoopSub (graph, tv, v, VisitFunc))
    
96.                 {
    
97.                     return 1;
    
98.                 }
    
99.             }
    
100.             /* At this line:
     
101.              * (1)If tv's color is already BLACK; Go ahead checking next arc;
     
102.              * (2)If the sub-tree of node tv has all been visited, mark as BLACK and check next arc;
     
103.              * Backward tv to to v's other adjacent node. So tv should be marked as black.
     
104.              * */
     
105.             MarkNodeColor (graph, tv, BLACK);
     
106.         }
     
107. 
     
108.         arc = arc->nextarc;
     
109.    }
     
110.    return 0;
     
111. }
     
112. 
     

复制代码

deadlylight

80楼的方法肯定是错的
a+y*b和a+p*b理论上可以相等
但是不要忘了，这个时候你的两个指针步长都是1，速度相同，永远都追不上的

thinkinnight

原帖由 deadlylight 于 2007-4-29 18:50 发表
80楼的方法肯定是错的
a+y*b和a+p*b理论上可以相等
但是不要忘了，这个时候你的两个指针步长都是1，速度相同，永远都追不上的

多谢指点
想了一下，的确是这里条件不够，有可能出现出现始终两个指针差n*b(n>0)圈的情况（并没有去找一个特殊的例子，但是我想了一下，这个情况应该是可能出现的），这样就会产生永远追不上的情况，那是否可以设置一个条件，记录下第一次相遇的那个节点，如果指针1又一次到达这个节点的时候，指针1暂时停止前进，而指针2向前b个节点呢？

win_hate

这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。


1、我的想法



设这些点的下标为 0, 1, 2, ...


看上面的图，红点是大步-小步法找到的。设起点到红点的长度为 i，环的长度为 b，则

从红点出发，每 b 步后，都回到红点。如果我们让指针从红点出发，回退 b 步，得到的点标记为黄色。此时，从红点或黄点出发，b 步后都落在红点上。容易看出，用两个指针，分别从红，黄两点出发，步幅为 1，则它们的首个重合点就是环首。

回退 b 步得到的点在实现上可以通过从起点走 i-b 步得到。 由于 2i>=i+b, i-b 总是合法的。

我在前面帖子给出的方法与这个是一样的，只是陈述方式不同，而且前面的帖子符号有点混淆。

另外 i=0 (mod b) 总是成立的，因为 i = 2i (mod b)。 所以我们有  b|i


2、对 Emacsnw 的方法的解释
用两个指针一个指向第 i 点，另一个指向第 2i 点，而它们都指向红点。现在它们都回退 i 步(步幅 1)，则一个指针退到起点0，另一个指针退到 i 点。 此时让两个指针按步幅1 向前走直到相交就是环首。

设置退到 0 点的指针叫 p，停留在 i 点的叫 q， 则 q 每走 b 步都留在红点，所以我们可以把 p 的起点提前 b 的一个倍数而不影响结果。这就是我在前面帖子中的做法，用 i 去除以 b.

[ 本帖最后由 win_hate 于 2007-4-30 10:12 编辑 ]

softsongs

你这个图画的还有才了，呵呵。

原帖由 win_hate 于 2007-4-30 09:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。


1、 ...

shaohui

win_hate,Emacsnw 的连个方法我觉得是一样的。应该是最好的解法了.时间是O(n),空间(1)

thinkinnight

原帖由 win_hate 于 2007-4-30 09:51 发表
这个帖子这么长了。看了后面的回复，觉得很多朋友没有理解 Emacsnw 的方法。其实他的方法已经很简明了，相比之下我给出的解答则比较艰涩隐晦。现在把我的方法解释一次，顺带也把 emacsnw 的方法说一下。


1、 ...

学习了，是我没有理解清楚。