CCI_Q2.5

本文参考该作者文章当作编程笔记：

作者：Hawstein
出处：http://hawstein.com/posts/ctci-solutions-contents.html

给定一个循环链表，实现一个算法返回这个环的开始结点。

定义：

循环链表：链表中一个结点的指针指向先前已经出现的结点，导致链表中出现环。

例子：

输入：A -> B -> C -> D -> E -> C [结点C在之前已经出现过]

输出：结点C

思路：见原作者blog：http://hawstein.com/posts/2.5.html

CODE：

 1 #include<stdio.h>
 2 #include"list.h"
 3 #define N 10
 4 struct node *loopstart(struct node *head)
 5 {
 6     if(!head->next)return NULL;
 7     link fast=head,slow=head;
 8     while(fast->next)
 9     {
10         fast=Next(fast);
11         fast=Next(fast);
12         slow=Next(slow);
13         if(fast==slow)
14             break;
15     }
16     if(!fast||!fast->next)return NULL;
17     slow=head;
18     while(fast->next)
19     {
20         fast=Next(fast);
21         slow=Next(slow);
22         if(fast==slow)
23             break;
24     }
25     return fast;
26 }
27 int main()
28 {
29     struct node *head;
30     initNodes(&head);
31     int s[N]={3,2,1,3,5,6,2,6,3,1};
32     int i;
33     for(i=N-1;i>=0;--i)
34     {
35         insertNext(head,newNode(s[i]));
36     }
37     link p=head,q=head;
38     for(i=0;i<N;i++)//第4个点设为环形起点。
39     {
40         p=p->next;
41         if(i==3)
42             q=p;
43     }
44     p->next=q;//最后一个点指向环形起点。
45     p=loopstart(head);
46     if(p)
47         printf("%d
",Item(p));
48     return 0;
49 }