数据结构练级之路【链表带环问题】

一、链表带环问题的代码和几个经典的面试题（重点在于如何算入口点）

代码非常的简单，但是有几个关于带环问题的讲解就比较不好理解

1.有关链表是否带环的题目和代码

（较难且较经典）（有关链表带环的问题）（经典的引用了快慢指针的使用）（追击问题）
题目：给定一个链表，判断链表中是否有环。
意思：如果链表中有某一个结点，可以通过连续跟踪next指针再次到达，则链表中存在环，为了表示给定链表中的环，我们使用整数pos来表示链表尾链接到链表中的位置（索引从0开始），
如果pos的位置是-1.则在该链表中没有环，注意pos不作为参数进行传递，仅仅是为了标示链表的实际情况。
思路：使用快慢指针（slow和fast都从头结点开始，slow一次走一步，fast一次走两步，不带环fast就会为空，带环fast就会追上我的slow）；

实现：

bool hasCycle(struct ListNode* head)//有环就返回true无环就返回false
{
	struct ListNode* fast = head;
	struct ListNode* slow = head;
	while (fast && fast->next)//这个就是一次走两步，此时就会涉及到一个奇偶的问题，所以两个条件都要进行判断
	{
		slow = slow->next;
		fast = fast->next->next;

		if (slow == fast)//这步就是表示我追击到了（此时就是可以表明这个链表是带环的链表）
		{
			return true;
		}
	}

	return false;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.经典的带环问题1

问题：问为什么slow走一步，fast走两步最后一定可以相遇？

解答：因为假如fast在追击slow的时候（此时的fast已经入环了，然后假设此时它们之间的距离是N），因为此时的fast每次都比slow多走一步，所以此时的距离就会从N到N-1，这样一直走下去，N肯定可以变成0，所以肯定可以找到

3.经典带环问题2

问题：问假如fast此时不走两步而是走n步，此时还一定可以找到吗？

解答：答案首先是：不可以；原因：

假如此时的fast走的是3步，距离还是N，fast每次比slow多走2步，所以此时是N-2，N-4（所以就可以显然看出此时假如N是一个奇数就不能追到，只有当N是一个偶数的时候才可能追到），所以不一定可以追到，并且如果继续往下一圈走的时候，如果此时还是没有追到（那么此时的这个fast就不可能找到slow了）；因为：假如此时的N是一个奇数，然后此时就会导致fast在slow的前面（如果当我的fast在slow的前面时，此时的fast和slow的距离就发生的大改变，从小变成了最大，因为此时fast在前，所以距离就变成了环的长度-1（C-1）），所以假如C-1是一个奇数就会导致N是奇数（那么此时就又是那个道理，N是奇数就追不到），只有当C-1（N）是一个偶数时，才有可能追上，所以关键追上与追不上就是取决去（环的长度是奇数还是偶数），但是还要注意这边是有一个减1的，所以环的大小是偶数就追不到，环的大小是一个奇数就可以找到

4.如何求环的入口点？（理论解答）

第一种方法：

环的入口点的思路：一个指针从相遇点开始走，一个指针从链表头结点开始走，它们会在环的入口点相遇
为什么是这样的呢？所以下面我们就来介绍一下为什么一个指针从相遇点开始走，一个指针从链表头结点开始走，它们会在环的入口点相遇呢？

由上述的思路我们此时假设：
从头结点到入环点的距离是：L
环的长度是:C
慢指针在环中走的距离为：X
走的圈数是：N
所以此时在追上到相遇的过程中
慢指针走的距离：L+X
快指针走的距离：L+X+C 而是 L+X+N*C
又因为快指针走的路程是慢指针的2倍
所以此时就可以得到一个等式：
2 * (L+X) = L+X+N * C
变形得到：L+X=N * C
变形得到：L=N * C-X
变形得到：L=(N-1)*C+C-X
所以此时通过这个表达式，此时就可以得到 L=C-X；因为此时的N-1可以看成是一个整数倍的圈数，就可以看成是在循环，其实还是从这个位置开始
所以就得到了 L=C-X; 所以我们就证明了这句话 ：一个指针从相遇点开始走，一个指针从链表头结点开始走，它们最终会在环的入口点相遇。

下面是图示：

具体求入口点的代码：

struct ListNode* detectCycle(struct ListNode* head)
{
	struct ListNode* slow = head;
	struct ListNode* fast = head;
	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
		if (slow == fast)//这个条件会成立的话就表示我链表是有环的，并且此时追到了
		{
			struct ListNode* meet = slow;
			//此时的这个循环中的结论就是由我的公式证明出来的
			while (meet != head)
			{
				meet = meet->next;
				head = head->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
25

第二种方法：

就是可以先算出这个环的相遇点，然后把这个点给断开，然后就可以非常巧妙的把这个判断环的相遇点的问题给转换成求交点的问题（但是代码实现起来优点困难）

二、总结：

以上就是有关链表带环的一系列问题，建议反复画图理解