快慢指针判断链表是否有环

一、快慢指针的思想：
  • 定义快慢指针fast和slow，起始位于链表头部，规定fast每次后移2步，slow后移1步
  • 若fast遇到null节点，则链表一定无环，结束
  • 若链表有环，fast和slow一定会相遇
  • 当fast和slow相遇时，创建相遇指针ptr。现在重新开始，相遇指针ptr和链表头步指针slow分别开始每次向后移1步，最终slow和ptr会在环入口处相遇。
二、疑问
  • 为什么fast和slow一定会相遇？
  • fast和slow相遇时，slow指针是否绕环超过一圈？
  • slow和ptr相遇时节点为啥是环入口？
  • fast指针为什么每次移动2步，3、4、5 、…n步可不可以？
三、问题解答

注意前三个问题是以快指针每次移动2步为前提。

  1. 那么为什么fast和slow一定会相遇呢，用直观的感受来说就像操场上两个人在跑步，一个是常年跑马拉松的高手，一个是大重量肥宅，假设他们一直跑，大重量阿宅一定会被马拉松高手“套圈”，这样他们就相遇了。

    但这里的问题略有不同，链表中每次移动一格，可能会存在快指针跳跃式穿过慢指针的情况，有以下几种情况（快指针在慢指针之后追赶）:

    • 相距1格，下次移动一定相遇
    • 相距两格，下次移动后相距1格
    • 其他时刻，每次环内移动，距离会缩短1，直至相距2格
      通过分析得出fast指针和slow指针一定会相遇，但当fast指针的步数>2时可能就会存在正好fast越过slow的情况

  2. fast指针和slow指针因为慢指针是一步一步走，所以它可以遍历链表中的每一个点，我们在环里找一个合适的点，便于证明。
    设y为s的整数倍，且y>x；这里就是在环里找一个点，假设慢指针现在位于这个点；那么快指针走过的长度肯定为ky。那么两者路径之差为(k-1)y；因为y是s的整数倍，所以肯定能遇见。相遇时，slow指针是否绕环超过一圈

    • 当整个链表就是一个环的状态下，当slow移动到环尾，fast刚好“追上”slow。
    • 当链表中除了环还有多余的“冲刺”进入环的部分时，fast这时会先进入环，当slow达到环入口时，可能正好碰见绕了n圈的环，此种情况slow绕环0圈。也可能与fast “错开“，此时可以看做fast已经抢跑了一段距离，那么要追上slow就轻松得多，不可能让slow跑完一整圈的。
      由此能得出当fast和slow相遇时slow不可能绕环超过一圈

  3. 下面来说明slow和ptr相遇时节点为啥是环入口
    图中蓝色为快指针，红色为慢指针，设头结点到环入口点的距离为a。当慢指针到达环入口点时，快指针到达①处，由此快慢指针在②处相遇，设环入口点到相遇处的距离为Δ，环长为r，相遇时fast绕过了n圈则有2 (a+Δ) = a + n*r + Δ得出a = n*r - Δ，所以，重点来了，头结点到环的入口点的距离等于n倍环长减去环的入口点到相遇点的距离。因此我们可以设一个指针，一个指向头结点head，一个指向相遇点ptr，两个指针同步移动，相遇点即为入口点。


代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
LNode* FindLoopStart(LNode *head){
	LNode *fast = head, *slow = head; // 设置快慢指针
	while(fast != NULL && fast->next != NULL){
		slow = slow->next;         //每次走一步
		fast = fast->next->next;   //每次走两步
		if(slow == fast) break;
	}
	if(slow==NULL||fast->next==NULL)
		return NULL;
	LNode *p1 = head, *p2 = slow;
	while(p1!=p2){
		p1 = p1->next;
		p2 = p2->next;
	}
	return p1;
}

  1. 快指针步数为k行不行
    慢指针步长为1，快指针步长为k，环的入口到链表起点的距离为a，环的长度为r。因为慢指针是一步一步走，所以它可以遍历链表中的每一个点，我们在环里找一个合适的点，便于证明。
    设y为r的整数倍n*r，且y>a；这里就是在环里找一个点，假设慢指针现在位于这个点；那么快指针走过的长度肯定为ky。那么两者路径之差为(k-1)y；因为y是s的整数倍，所以肯定能遇见。