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

星塵細(xì)雨

兩個(gè)步進(jìn)不一樣的指針是個(gè)好辦法。

但如果有好的內(nèi)存分配策略的話，應(yīng)該可以簡(jiǎn)化這個(gè)問題。

比如說，鏈表的每一項(xiàng)，從前到后，分配的內(nèi)存地址都是有序的的話，
只需要把list->next指針和list本身比較一下看是否符合順序就知道是否找到節(jié)點(diǎn)了。

不過這個(gè)內(nèi)存分配方法不好辦。

deadlylight

首先用1步長(zhǎng)2步長(zhǎng)的方法判斷是否有環(huán)存在O(n)。
如果有環(huán)，那就再從頭開始，看每個(gè)節(jié)點(diǎn)的next是不是空。如果是空，就是我們要找的節(jié)點(diǎn)；不是空的話，就把它置空。O(n)
以樓主的例子，到8的時(shí)候，前面的節(jié)點(diǎn)的next都是空了，然后8指向3，發(fā)現(xiàn)3的next為空，就找到了最終結(jié)果。

這樣的方法復(fù)雜度時(shí)間O(n),空間O(1)
但是破環(huán)了原有的鏈表
如果想不破壞
就需要一個(gè)輔助鏈表保存原始鏈表的信息，這樣就需要O(n)的空間

所以最終結(jié)論是時(shí)間空間都是O(n)

jist12321

我想到一個(gè)新算法，不知道行不行得通，大家看一下，先是直接開一個(gè)空間，讓這整個(gè)空間的地址是連續(xù)的，然后根據(jù)上面的連表一個(gè)個(gè)考過去，因?yàn)榈刂肥沁B續(xù)的，所以當(dāng)出現(xiàn)一個(gè)指向的結(jié)構(gòu)體的地扯比自已小的時(shí)候，這時(shí)就出現(xiàn)了一個(gè)循環(huán)，也就是找到了樓主的循環(huán)點(diǎn)，可是這里有一個(gè)能點(diǎn)就是這個(gè)考的過程，我現(xiàn)在還沒想出來．大家看看，能不能實(shí)現(xiàn)。

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

deadlylight

原帖由 jist12321 于 2007-4-28 12:38 發(fā)表
我想到一個(gè)新算法，不知道行不行得通，大家看一下，先是直接開一個(gè)空間，讓這整個(gè)空間的地址是連續(xù)的，然后根據(jù)上面的連表一個(gè)個(gè)考過去，因?yàn)榈刂肥沁B續(xù)的，所以當(dāng)出現(xiàn)一個(gè)指向的結(jié)構(gòu)體的地扯比自已小的時(shí)候，這時(shí) ...

為什么地址小的時(shí)候就可以斷定是循環(huán)呢，這種說法沒有任何根據(jù)

jist12321

原帖由 deadlylight 于 2007-4-28 12:56 發(fā)表


為什么地址小的時(shí)候就可以斷定是循環(huán)呢，這種說法沒有任何根據(jù)

對(duì)不起，后面沒看下去，剛剛轉(zhuǎn)回去看了一下，行不通。不過，一步二步法是絕對(duì)可以的，而且我認(rèn)認(rèn)應(yīng)該是時(shí)間復(fù)雜度是最小的了。

jist12321

原帖由 星塵細(xì)雨 于 2007-4-28 10:05 發(fā)表
兩個(gè)步進(jìn)不一樣的指針是個(gè)好辦法。

但如果有好的內(nèi)存分配策略的話，應(yīng)該可以簡(jiǎn)化這個(gè)問題。

比如說，鏈表的每一項(xiàng)，從前到后，分配的內(nèi)存地址都是有序的的話，
只需要把list->next指針和list本身比較一 ...

我想的方法跟你差不多啊，可是這個(gè)內(nèi)存分配有序的話就不存在鏈表一說，直接用數(shù)組了，像我說用考出整個(gè)鏈表更可笑，鏈表尾都不知道，怎么可能知道考哪里為止。做了一回傻瓜。

zx_wing

各位給了很多方法，可惜沒給代碼，小弟也就沒認(rèn)真看了。
長(zhǎng)期做系統(tǒng)程序，算法思維僵化了，想從現(xiàn)在開始鍛煉鍛煉，我就直接貼代碼了。
算法很笨，先用不同步長(zhǎng)前進(jìn)找到圈，然后把圈中所有元素存到數(shù)組中（c99動(dòng)態(tài)數(shù)組），最后再從鏈表頭走一遍，第一個(gè)在數(shù)組中存在的元素就是圈的首節(jié)點(diǎn)。
不會(huì)算復(fù)雜度，估計(jì)是O(n^3)左右了，太爛了，開始練習(xí)算法。

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;
   

復(fù)制代碼

1. 
   
2. //不用細(xì)看，用來產(chǎn)生帶圈的鏈表。
   
3. //len參數(shù)指定鏈表長(zhǎng)度，loop_pos指定最后一個(gè)元素指向鏈表中的第幾個(gè)元素。
   
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. 
    

復(fù)制代碼

1. 
   
2. //鏈表打印函數(shù)，不用細(xì)看
   
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. }
    

復(fù)制代碼

1. 
   
2. //用來找圈的頭節(jié)點(diǎn)，被find_loop調(diào)用
   
3. //addr保存的是圈中所有節(jié)點(diǎn)的地址，head指向鏈表頭，lo_len表示圈中有多少個(gè)節(jié)點(diǎn)
   
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.            //先找出圈中有多少個(gè)節(jié)點(diǎn)
    
36.             while ( t1 != t2 )
    
37.             {
    
38.                 lo_len ++;
    
39.                 t1 = t1->next;
    
40.             }
    
41.            //把圈中的所有幾點(diǎn)存入數(shù)組
    
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.             //找出圈中的第一個(gè)節(jié)點(diǎn)
    
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. }
    

復(fù)制代碼

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. }
   

復(fù)制代碼

星塵細(xì)雨

怎么沒有根據(jù)？

這個(gè)是有個(gè)前提條件的！只是滿足這個(gè)前提條件比較困難而已。

thinkinnight

原帖由 deadlylight 于 2007-4-28 12:17 發(fā)表
首先用1步長(zhǎng)2步長(zhǎng)的方法判斷是否有環(huán)存在O(n)。
如果有環(huán)，那就再從頭開始，看每個(gè)節(jié)點(diǎn)的next是不是空。如果是空，就是我們要找的節(jié)點(diǎn)；不是空的話，就把它置空。O(n)
以樓主的例子，到8的時(shí)候，前面的節(jié)點(diǎn)的ne ...

我覺得這個(gè)算法是可以的，還有那個(gè)大步小步的，應(yīng)該也是可以的，不過對(duì)于推出的公式，還不能確定是否正確，因?yàn)榇笮〔讲灰欢ㄊ且蝗�，而是大步m圈，小步n圈之后才相遇的，想到這個(gè)就暈了，就搞不清公式是否正確，不過應(yīng)該大小步是能解這個(gè)問題的。
再想想。。。

thinkinnight

原帖由 emacsnw 于 2007-2-6 04:27 發(fā)表
想了一下，似乎下面的算法可以：O(1)空間，O(n)時(shí)間。
兩個(gè)額外指針p1, p2，開始都指向頭S。設(shè)需要找到的循環(huán)部分第一個(gè)結(jié)點(diǎn)的位置為A，S到A的距離為x (x可能為0），鏈表的循環(huán)部分長(zhǎng)度為y (y > 0)。

算法 ...

這個(gè)算法應(yīng)該是看懂了，畫了個(gè)圖分析了一下，似乎是這樣的，如果還是有什么地方不對(duì)，請(qǐng)指出來。還是很有意思的一道題目。