- 論壇徽章:
- 0
|
各位給了很多方法,可惜沒給代碼,小弟也就沒認(rèn)真看了。
長(zhǎng)期做系統(tǒng)程序,算法思維僵化了,想從現(xiàn)在開始鍛煉鍛煉,我就直接貼代碼了。
算法很笨,先用不同步長(zhǎng)前進(jìn)找到圈,然后把圈中所有元素存到數(shù)組中(c99動(dòng)態(tài)數(shù)組),最后再?gòu)逆湵眍^走一遍,第一個(gè)在數(shù)組中存在的元素就是圈的首節(jié)點(diǎn)。
不會(huì)算復(fù)雜度,估計(jì)是O(n^3)左右了, 太爛了,開始練習(xí)算法。
- #include <stdio.h>
- #include <stdlib.h>
-
- typedef struct list
- {
- int val;
- struct list *next;
- } list_t;
復(fù)制代碼
- //不用細(xì)看,用來產(chǎn)生帶圈的鏈表。
- //len參數(shù)指定鏈表長(zhǎng)度,loop_pos指定最后一個(gè)元素指向鏈表中的第幾個(gè)元素。
- //loop_pos如果大于len,則鏈表尾指向鏈表頭。
- list_t *pro_list(int len, int loop_pos)
- {
- list_t *head = malloc(sizeof(list_t));
- list_t *t = head, *n = head;
- int i;
- head->val = 0;
-
- for ( i=1; i<len; i++ )
- {
- list_t *m = malloc(sizeof(list_t));
- m->val = i;
- t->next = m;
- t = m;
- }
-
- if ( loop_pos <= len )
- for ( i=0; i<loop_pos; i++ )
- n = n->next;
-
- t->next = n;
-
- return head;
- }
-
復(fù)制代碼
- //鏈表打印函數(shù),不用細(xì)看
- void print_list(list_t *head)
- {
- list_t *t = head;
- while (1)
- {
- printf("val:%d, addr:%p\n", t->val, t);
- if ( NULL == t->next )
- break;
-
- t = t->next;
- }
- }
復(fù)制代碼
- //用來找圈的頭節(jié)點(diǎn),被find_loop調(diào)用
- //addr保存的是圈中所有節(jié)點(diǎn)的地址,head指向鏈表頭,lo_len表示圈中有多少個(gè)節(jié)點(diǎn)
- list_t *find_loop_begin(list_t *addr[], list_t *head, int lo_len)
- {
- int i;
- list_t *t = head;
-
- while (1)
- {
- for ( i=0; i<lo_len; i++ )
- if ( addr[i] == t )
- return addr[i];
-
- t = t->next;
- }
-
- // should not be here
- return NULL;
- }
- list_t *find_loop(list_t *head)
- {
- list_t *t1 = head;
- list_t *t2 = head->next;
-
- while (1)
- {
- if ( t1 == t2 )
- {
- int lo_len = 1;
- int i = 1;
- t1 = t1->next;
- //先找出圈中有多少個(gè)節(jié)點(diǎn)
- while ( t1 != t2 )
- {
- lo_len ++;
- t1 = t1->next;
- }
- //把圈中的所有幾點(diǎn)存入數(shù)組
- list_t *addr[lo_len];
- addr[0] = t2;
- t1 = t2->next;
- while ( t1 != t2 )
- {
- addr[i++] = t1;
- t1 = t1->next;
- }
- //找出圈中的第一個(gè)節(jié)點(diǎn)
- return find_loop_begin(addr, head, lo_len);
- }
- t1 = t1->next;
- t2 = t2->next->next;
- }
-
- return t1;
- }
復(fù)制代碼
- int main()
- {
- list_t *head = pro_list(20, 11);
- list_t *lo = find_loop(head);
- printf("val:%d, addr:%p\n", lo->val, lo);
- //print_list(head);
-
- }
復(fù)制代碼 |
|