这个问题遇到过很多次了，但是并不是说每次都很清楚。所以这次用golang的代码来实现一遍，加深理解与记忆。
如果一个链表上不存在环，那么一定能够遍历完链表中所有的Node节点；如果存在环，那么可以想象成存在一个圆形操场。在一个圆里面，如果有两个人，行走的速度不一样，那么一定会有相遇的那一刻。最佳的解法便是基于此想法，当然也有其他的解法，比如说将每个遍历的节点放进一个set里面，如果存在过，那么就存在环。
数据结构：
1
2
3
4
| type Node struct {
index int
next *Node
}
|
构建链表，随机选择是否生成环
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
| func createNodeList() *Node{
rand.Seed(time.Now().Unix())
length := rand.Intn(100) + 1
head := new(Node)
var tail *Node
for idx ,curNode := 1, head; idx <= length; idx ++ {
curNode.index = idx
if idx != length {
curNode.next = new(Node)
curNode = curNode.next
} else {
tail = curNode
}
}
buildRing := rand.Intn(2)
if buildRing == 0 {
enterRingIndex := rand.Intn(length) + 1
enterRingNode := head
for idx:= 2; idx <= enterRingIndex; idx ++{
enterRingNode = enterRingNode.next
}
tail.next = enterRingNode
fmt.Println("length : ", length, ", enter ring index : ", enterRingIndex, ", Ring length : ", length - enterRingIndex + 1)
} else {
fmt.Println("don't build ring")
}
return head
}
|
输出链表，用于debug
1
2
3
4
5
6
| func outputNodeList(head * Node) {
for head != nil {
fmt.Print(head.index, " ")
head = head.next
}
}
|
使用两个下标，用于抽象表示圆形操场中的两个人，leader走前面，每次走两步，follower走后面，每次走一步，如果相遇，返回相遇时的Node节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| func nodeListExistRing(head * Node) *Node {
leader, follower := head, head
for leader != nil && follower != nil {
leader = leader.next
if leader == nil {
return nil
}
leader = leader.next
follower = follower.next
if (leader == follower) {
return leader
}
}
return nil
}
|
如果链表中存在环，那么环的长度就等于：follower再走一圈时走过的步长。
1
2
3
4
5
6
7
8
9
| func calRingLength(meetNode * Node) int {
curNode := meetNode
curNode = curNode.next
count := 1
for ; curNode != meetNode; count ++ {
curNode = curNode.next;
}
return count
}
|
如果链表存在环，那么入环点等于将leader指向head后，并以每次一步的速度往前，直到与follower再次相遇，此时的节点便是入环点。
如何证明上面的步骤是正确的？
也就是说，入环时走过的路程，等于S2加上(S1+S2)的整数倍，如果leader步长变成1，并且从A点出发到达B点，那么走过的路程D，一定会等于S2+(n-1)(S1 + S2)，也就是说一定会在B点相遇。B点即入环点。
1
2
3
4
5
6
7
8
9
| func calEnterRingIndex(meetNode * Node, head * Node) int {
var enterRingIndex = 0;
for head != meetNode {
head = head.next
meetNode = meetNode.next
enterRingIndex ++
}
return enterRingIndex + 1
}
|
启动类，将前面过程，按照想要的逻辑拼装在一起。
1
2
3
4
5
6
7
8
9
| func main() {
head := createNodeList()
meetNode := nodeListExistRing(head)
if meetNode == nil {
outputNodeList(head)
} else {
fmt.Println("RING EXIST!", ", Ring length: ", calRingLength(meetNode), ", Enter Ring Index : ", calEnterRingIndex(meetNode, head))
}
}
|
附录：
文中公式、图及推算过程的latex源码:
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
| \begin{tikzpicture}
\draw(0, 0) circle (1.5cm);
\coordinate[label = above:$O$] (O) at (0, 0);
\node at(0, 0)[circle,fill,inner sep=1pt]{};
\coordinate[label = right:$C$] (C) at (-30:1.5);
\node at(C)[circle,fill,inner sep=1pt]{};
\coordinate[label = below right:$S_1$] (S1) at (-60:1.5);
\coordinate[label = left:$S_2$] (S2) at (120:1.5);
\coordinate[label = below: $B$] (B) at (-90:1.5);
\node at(B)[circle,fill,inner sep=1pt]{};
\coordinate[label = below: $A$] (A) at (-7, -1.5);
\node at(A)[circle,fill,inner sep=1pt]{};
\draw (A) -- (B) node[above, midway] (line) {$D$};
\end{tikzpicture}
设n为leader与follower在相遇前，比follower多走的圈数，那么便存在
\[ 2(D + S_1) = D + S_1 + n * (S_1 + S_2) \]
化简得：
\[ 2*D + 2*S_1 = D + S_1 + n * (S_1 + S_2) \]
\[ D + S_1 = n * (S_1 + S_2) \]
\[ D = n * (S_1 + S_2) - S_1 \]
\[ D = (n - 1) * (S_1 + S_2) + S_1 + S_2 - S_1 \]
即：
\[ D = (n - 1) * (S_1 + S_2) + S_2 \]
|
参考：https://zouyu4524.github.io/blog/tikz-plot/
