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

星尘细雨

两个步进不一样的指针是个好办法。

但如果有好的内存分配策略的话，应该可以简化这个问题。

比如说，链表的每一项，从前到后，分配的内存地址都是有序的的话，
只需要把list->next指针和list本身比较一下看是否符合顺序就知道是否找到节点了。

不过这个内存分配方法不好办。

deadlylight

首先用1步长2步长的方法判断是否有环存在O(n)。
如果有环，那就再从头开始，看每个节点的next是不是空。如果是空，就是我们要找的节点；不是空的话，就把它置空。O(n)
以楼主的例子，到8的时候，前面的节点的next都是空了，然后8指向3，发现3的next为空，就找到了最终结果。

这样的方法复杂度时间O(n),空间O(1)
但是破环了原有的链表
如果想不破坏
就需要一个辅助链表保存原始链表的信息，这样就需要O(n)的空间

所以最终结论是时间空间都是O(n)

jist12321

我想到一个新算法，不知道行不行得通，大家看一下，先是直接开一个空间，让这整个空间的地址是连续的，然后根据上面的连表一个个考过去，因为地址是连续的，所以当出现一个指向的结构体的地扯比自已小的时候，这时就出现了一个循环，也就是找到了楼主的循环点，可是这里有一个能点就是这个考的过程，我现在还没想出来．大家看看，能不能实现。

[ 本帖最后由 jist12321 于 2007-4-28 12:39 编辑 ]

deadlylight

原帖由 jist12321 于 2007-4-28 12:38 发表
我想到一个新算法，不知道行不行得通，大家看一下，先是直接开一个空间，让这整个空间的地址是连续的，然后根据上面的连表一个个考过去，因为地址是连续的，所以当出现一个指向的结构体的地扯比自已小的时候，这时 ...

为什么地址小的时候就可以断定是循环呢，这种说法没有任何根据

jist12321

原帖由 deadlylight 于 2007-4-28 12:56 发表


为什么地址小的时候就可以断定是循环呢，这种说法没有任何根据

对不起，后面没看下去，刚刚转回去看了一下，行不通。不过，一步二步法是绝对可以的，而且我认认应该是时间复杂度是最小的了。

jist12321

原帖由 星尘细雨 于 2007-4-28 10:05 发表
两个步进不一样的指针是个好办法。

但如果有好的内存分配策略的话，应该可以简化这个问题。

比如说，链表的每一项，从前到后，分配的内存地址都是有序的的话，
只需要把list->next指针和list本身比较一 ...

我想的方法跟你差不多啊，可是这个内存分配有序的话就不存在链表一说，直接用数组了，像我说用考出整个链表更可笑，链表尾都不知道，怎么可能知道考哪里为止。做了一回傻瓜。

zx_wing

各位给了很多方法，可惜没给代码，小弟也就没认真看了。
长期做系统程序，算法思维僵化了，想从现在开始锻炼锻炼，我就直接贴代码了。
算法很笨，先用不同步长前进找到圈，然后把圈中所有元素存到数组中（c99动态数组），最后再从链表头走一遍，第一个在数组中存在的元素就是圈的首节点。
不会算复杂度，估计是O(n^3)左右了，太烂了，开始练习算法。

1. 
   
2. #include <stdio.h>
   
3. #include <stdlib.h>
   
4. 
   
5. typedef struct list
   
6. {
   
7.     int val;
   
8.     struct list *next;
   
9. } list_t;
   

复制代码

1. 
   
2. //不用细看，用来产生带圈的链表。
   
3. //len参数指定链表长度，loop_pos指定最后一个元素指向链表中的第几个元素。
   
4. //loop_pos如果大于len,则链表尾指向链表头。
   
5. list_t *pro_list(int len, int loop_pos)
   
6. {
   
7.     list_t *head = malloc(sizeof(list_t));
   
8.     list_t *t = head, *n = head;
   
9.     int i;
   
10.     head->val = 0;
    
11. 
    
12.     for ( i=1; i<len; i++ )
    
13.     {   
    
14.         list_t *m = malloc(sizeof(list_t));
    
15.         m->val = i;
    
16.         t->next = m;
    
17.         t = m;
    
18.     }   
    
19. 
    
20.     if ( loop_pos <= len )
    
21.         for ( i=0; i<loop_pos; i++ )
    
22.             n = n->next;
    
23. 
    
24.     t->next = n;
    
25.    
    
26.     return head;
    
27. }
    
28. 
    

复制代码

1. 
   
2. //链表打印函数，不用细看
   
3. void print_list(list_t *head)
   
4. {
   
5.     list_t *t = head;
   
6.     while (1)
   
7.     {
   
8.         printf("val:%d, addr:%p\n", t->val, t);
   
9.         if ( NULL == t->next )
   
10.             break;
    
11. 
    
12.         t = t->next;
    
13.     }
    
14. }
    

复制代码

1. 
   
2. //用来找圈的头节点，被find_loop调用
   
3. //addr保存的是圈中所有节点的地址，head指向链表头，lo_len表示圈中有多少个节点
   
4. list_t *find_loop_begin(list_t *addr[], list_t *head, int lo_len)
   
5. {
   
6.     int i;
   
7.     list_t *t = head;
   
8. 
   
9.     while (1)
   
10.     {
    
11.         for ( i=0; i<lo_len; i++ )
    
12.             if ( addr[i] == t )
    
13.                 return addr[i];
    
14. 
    
15.         t = t->next;
    
16.     }
    
17. 
    
18.     // should not be here
    
19.     return NULL;
    
20. }
    
21. 
    
22. 
    
23. list_t *find_loop(list_t *head)
    
24. {
    
25.     list_t *t1 = head;
    
26.     list_t *t2 = head->next;
    
27. 
    
28.     while (1)
    
29.     {
    
30.         if ( t1 == t2 )
    
31.         {
    
32.             int lo_len = 1;
    
33.             int i = 1;
    
34.             t1 = t1->next;
    
35.            //先找出圈中有多少个节点
    
36.             while ( t1 != t2 )
    
37.             {
    
38.                 lo_len ++;
    
39.                 t1 = t1->next;
    
40.             }
    
41.            //把圈中的所有几点存入数组
    
42.             list_t *addr[lo_len];
    
43.             addr[0] = t2;
    
44.             t1 = t2->next;
    
45.             while ( t1 != t2 )
    
46.             {
    
47.                 addr[i++] = t1;
    
48.                 t1 = t1->next;
    
49.             }
    
50.             //找出圈中的第一个节点
    
51.             return find_loop_begin(addr, head, lo_len);
    
52.         }
    
53.         t1 = t1->next;
    
54.         t2 = t2->next->next;
    
55.     }
    
56. 
    
57.     return t1;
    
58. }
    

复制代码

1. 
   
2. int main()
   
3. {
   
4.     list_t *head = pro_list(20, 11);
   
5.     list_t *lo = find_loop(head);
   
6.     printf("val:%d, addr:%p\n", lo->val, lo);
   
7.     //print_list(head);
   
8. 
   
9. }
   

复制代码

星尘细雨

怎么没有根据？

这个是有个前提条件的！只是满足这个前提条件比较困难而已。

thinkinnight

原帖由 deadlylight 于 2007-4-28 12:17 发表
首先用1步长2步长的方法判断是否有环存在O(n)。
如果有环，那就再从头开始，看每个节点的next是不是空。如果是空，就是我们要找的节点；不是空的话，就把它置空。O(n)
以楼主的例子，到8的时候，前面的节点的ne ...

我觉得这个算法是可以的，还有那个大步小步的，应该也是可以的，不过对于推出的公式，还不能确定是否正确，因为大小步不一定是一圈，而是大步m圈，小步n圈之后才相遇的，想到这个就晕了，就搞不清公式是否正确，不过应该大小步是能解这个问题的。
再想想。。。

thinkinnight

原帖由 emacsnw 于 2007-2-6 04:27 发表
想了一下，似乎下面的算法可以：O(1)空间，O(n)时间。
两个额外指针p1, p2，开始都指向头S。设需要找到的循环部分第一个结点的位置为A，S到A的距离为x (x可能为0），链表的循环部分长度为y (y > 0)。

算法 ...

这个算法应该是看懂了，画了个图分析了一下，似乎是这样的，如果还是有什么地方不对，请指出来。还是很有意思的一道题目。