解決單連結清單中的環問題

 給定一個單連結清單，隻給出頭指針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 &lt;stdlib.h&gt;</code>

<code>#include &lt;stdio.h&gt;</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-&gt;data = 1;</code>

<code>    </code><code>n1-&gt;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-&gt;data = 2;</code>

<code>    </code><code>n2-&gt;next = NULL;</code>

<code>    </code><code>p-&gt;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-&gt;data = 3;</code>

<code>    </code><code>n3-&gt;next = NULL;</code>

<code>    </code><code>p-&gt;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-&gt;data = 4;</code>

<code>    </code><code>n4-&gt;next = NULL;</code>

<code>    </code><code>p-&gt;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-&gt;data = 5;</code>

<code>    </code><code>n5-&gt;next = NULL;</code>

<code>    </code><code>p-&gt;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-&gt;data = 6;</code>

<code>    </code><code>n6-&gt;next = NULL;</code>

<code>    </code><code>p-&gt;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-&gt;next;</code>

<code>        </code><code>p2 = p2-&gt;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 &amp;&amp; p_fast-&gt;next)</code>

<code>        </code><code>p_slow = p_slow-&gt;next;</code>

<code>        </code><code>p_fast = p_fast-&gt;next-&gt;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-&gt;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-&gt;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，如需轉載請自行聯系原作者