环形链表问题（详细证明过程）_循环链表数学证明

判断链表是否有环（龟兔赛跑）

题目描述：给定一个链表，判断链表中是否有环。

思路：
 可以明确的是：若一个链表带环，那么用指针一直顺着链表遍历，最终会回到某个地方。
 我们可以定义两个指针（快慢指针），两个指针均从表头开始同时遍历链表，快指针一次走两步，慢指针一次走一步。如果链表带环，那么快慢指针一定会相遇，否则快指针会先遍历完链表（遇到NULL）。
 若是你不明白为什么链表带环，快慢指针就一定会相遇，那么你可以想想龟兔赛跑：

代码：

struct ListNode {
	int val;
	struct ListNode *next;
};
bool hasCycle(struct ListNode *head) {
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast && fast->next)
	{
		fast = fast->next->next;//兔子走两步
		slow = slow->next;//乌龟走一步
		if (fast == slow)//兔子与乌龟相遇
			return true;
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

返回链表开始入环的第一个结点

题目描述：给定一个链表，返回链表开始入环的第一个结点。如果链表无环，则返回NULL。

 这不是一道简简单单的代码题，严格来说，这是一道数学推论题，若是不能得出最终推论，是不能很好的解决该问题的。

推论如下：

 根据最终推论可以得出结论：若一个指针从出发点开始走，另一个指针从相遇点开始走，则他们最终会在入口点处相遇。
代码：

struct ListNode {
	int val;
	struct ListNode *next;
};
struct ListNode *detectCycle(struct ListNode *head) {
	struct ListNode* fast = head;
	struct ListNode* slow = head;
	while (fast && fast->next)
	{
		slow = slow->next;//慢指针走一步
		fast = fast->next->next;//快指针走两步
		if (fast == slow)//相遇
		{
			struct ListNode* meet = fast;//相遇点
			while (head != meet)
			{
				head = head->next;//一个指针从出发点开始走
				meet = meet->next;//一个指针从相遇点开始走
			}
			return meet;//两个指针相遇，返回当前结点
		}
	}
	return NULL;//链表不带环
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

面试还可能出现的问题

问题一：为什么慢指针走一步，快指针走两步，他们一定会在环里面相遇？会不会永远追不上？请证明。

不会永远追不上，证明如下：

问题二：那么慢指针走一步，快指针走三步？走四步？或是走n步行不行？为什么？请证明。

不行，这样可能会追不上，证明如下：

总结一下：
 当慢指针走一步，快指针走三步时。若慢指针进环时与快指针之间的距离为奇数，并且环的周长恰好为偶数，那么他们会一直在环里面打转转，永远不会相遇。
（当慢指针走一步，快指针走四步或是走n步时，证明过程类似）