给定一个单链表，只给出头指针h：
如何判断是否存在环？
如何知道环的长度？
如何找出环的连接点在哪里？
带环链表的长度是多少？
问题1 如何判断是否有环
使用追赶的方法，设定两个指针slow、fast，从头指针开始，每次分别前进1步、2步。如存在环，则两者相遇；如不存在环，fast遇到NULL退出。
问题2 如何判断环的长度
在相遇点出同时出发，fast指针和slow指针再次相遇时，slow指针走过的点的个数就是环的长度。试问会不会slow在不到一圈的地方两者相遇呢？不会，因为假设slow走s,则fast走2s。二者相遇则二者距离必相差圈数的倍数，即：2s-s = k*圈距离=s。此时k=1。因此得出结论：从相遇到再次相遇，slow再走完整的一圈。
问题3 如何找出环的连接点
定理：碰撞点p到连接点的距离=头指针到连接点的距离，因此，分别从碰撞点、头指针开始走，相遇的那个点就是连接点。
证明：
链表形状类似数字6。
假设甩尾（在环外）长度为 a（结点个数），环内长度为 b 。
则总长度（也是总结点数）为 a+b 。
从头开始，0 base 编号。
将第 i 步访问的结点用 S(i) 表示。i = 0, 1 ...
当 i＜a 时，S(i)=i ；
当 i≥a 时，S(i)=a+(i-a)%b 。
分析追赶过程。
两个指针分别前进，假定经过 x 步后，碰撞。则有：S(x)=S(2x)
由环的周期性有：2x=tb+x 。得到 x=tb 。
另，碰撞时，必须在环内，不可能在甩尾段，有 x>=a 。
连接点为从起点走 a 步，即 S(a)。
S(a) = S(tb+a) = S(x+a)。
得到结论：从碰撞点 x 前进 a 步即为连接点。
根据假设易知 S(a-1) 在甩尾段，S(a) 在环上，而 S(x+a) 必然在环上。所以可以发生碰撞。 又，同为前进 a 步，同为连接点，所以必然发生碰撞。
综上，从 x 点和从起点同步前进，第一个碰撞点就是连接点。
问题4 带环链表的长度是多少
问题2知道环的长度，问题3知道环外边的长度。两者相加即为总长度。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
<code>#include <stdlib.h></code>
<code>#include <stdio.h></code>
<code>typedef</code> <code>struct</code> <code>node</code>
<code>{</code>
<code> </code><code>int</code> <code>data;</code>
<code> </code><code>struct</code> <code>node *next;</code>
<code>}node;</code>
<code>node *Create_list() </code><code>//建立链表</code>
<code> </code><code>node *p_return, *p;</code>
<code> </code><code>p_return = NULL;</code>
<code> </code><code>node *n1 = (node *)</code><code>malloc</code><code>(</code><code>sizeof</code><code>(node));</code>
<code> </code><code>n1->data = 1;</code>
<code> </code><code>n1->next = NULL;</code>
<code> </code><code>p = n1;</code>
<code> </code><code>p_return = p;</code>
<code> </code><code>node *n2 = (node *)</code><code>malloc</code><code>(</code><code>sizeof</code><code>(node));</code>
<code> </code><code>n2->data = 2;</code>
<code> </code><code>n2->next = NULL;</code>
<code> </code><code>p->next = n2;</code>
<code> </code><code>p = n2;</code>
<code> </code><code>node *n3 = (node *)</code><code>malloc</code><code>(</code><code>sizeof</code><code>(node));</code>
<code> </code><code>n3->data = 3;</code>
<code> </code><code>n3->next = NULL;</code>
<code> </code><code>p->next = n3;</code>
<code> </code><code>p = n3;</code>
<code> </code><code>node *n4 = (node *)</code><code>malloc</code><code>(</code><code>sizeof</code><code>(node));</code>
<code> </code><code>n4->data = 4;</code>
<code> </code><code>n4->next = NULL;</code>
<code> </code><code>p->next = n4;</code>
<code> </code><code>p = n4;</code>
<code> </code><code>node *n5 = (node *)</code><code>malloc</code><code>(</code><code>sizeof</code><code>(node));</code>
<code> </code><code>n5->data = 5;</code>
<code> </code><code>n5->next = NULL;</code>
<code> </code><code>p->next = n5;</code>
<code> </code><code>p = n5;</code>
<code> </code><code>node *n6 = (node *)</code><code>malloc</code><code>(</code><code>sizeof</code><code>(node));</code>
<code> </code><code>n6->data = 6;</code>
<code> </code><code>n6->next = NULL;</code>
<code> </code><code>p->next = n6;</code>
<code> </code><code>p = n6;</code>
<code> </code><code>return</code> <code>p_return;</code>
<code>}</code>
<code>node *find_in_node(node *p1, node *p2) </code><code>//找到入环的结点</code>
<code> </code><code>while</code><code>(p1 != p2)</code>
<code> </code><code>{</code>
<code> </code><code>p1 = p1->next;</code>
<code> </code><code>p2 = p2->next;</code>
<code> </code><code>}</code>
<code> </code><code>return</code> <code>p1;</code>
<code>int</code> <code>get_out_len(node *p1, node *p2) </code><code>//计算出环外边的长度</code>
<code> </code><code>int</code> <code>num = 0;</code>
<code> </code><code>num++;</code>
<code> </code><code>return</code> <code>num;</code>
<code>node *check_loop(node *p) </code><code>//检查是否有环</code>
<code> </code><code>node *p_slow, *p_fast;</code>
<code> </code><code>p_slow = p;</code>
<code> </code><code>p_fast = p;</code>
<code> </code><code>int</code> <code>tag = 0;</code>
<code> </code><code>while</code><code>(p_slow && p_fast->next)</code>
<code> </code><code>p_slow = p_slow->next;</code>
<code> </code><code>p_fast = p_fast->next->next;</code>
<code> </code><code>if</code><code>(p_slow == p_fast)</code>
<code> </code><code>{</code>
<code> </code><code>tag = 1;</code>
<code> </code><code>break</code><code>;</code>
<code> </code><code>}</code>
<code> </code><code>if</code><code>(tag == 1)</code>
<code> </code><code>printf</code><code>(</code><code>"Have loop\n"</code><code>);</code>
<code> </code><code>return</code> <code>p_slow;</code>
<code> </code><code>else</code>
<code> </code><code>printf</code><code>(</code><code>"Not have loop\n"</code><code>);</code>
<code> </code><code>return</code> <code>NULL;</code>
<code>int</code> <code>get_len_loop(node *var_loop) </code><code>//得出环的长度</code>
<code> </code><code>node *p = var_loop->next;</code>
<code> </code><code>int</code> <code>num = 1;</code>
<code> </code><code>while</code><code>(p != var_loop)</code>
<code> </code><code>p = p->next;</code>
<code>int</code> <code>main()</code>
<code> </code><code>node *p = Create_list();</code>
<code> </code><code>node *coin_loop = check_loop(p);</code>
<code> </code><code>if</code><code>(coin_loop)</code>
<code> </code><code>int</code> <code>len_loop = get_len_loop(coin_loop);</code>
<code> </code><code>printf</code><code>(</code><code>"Length of Loop is:%d\n"</code><code>, len_loop);</code>
<code> </code><code>node *in_node = find_in_node(p, coin_loop);</code>
<code> </code><code>int</code> <code>len_out = get_out_len(p, coin_loop);</code>
<code> </code><code>printf</code><code>(</code><code>"Length of out Loop is %d\n"</code><code>, len_out);</code>
<code> </code><code>printf</code><code>(</code><code>"Length of all is %d\n"</code><code>, len_out + len_loop);</code>
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3395347.html，如需转载请自行联系原作者