数据结构 - 如何找到有环单链表的环的入口位置（C++）

古城微笑少年丶 2022-04-22 01:06 110阅读 0赞

**分享一下我老师大神的人工智能教程！零基础，通俗易懂！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow]**

**也欢迎大家转载本篇文章。分享知识，造福人民，实现我们中华民族伟大复兴！**

template<class T>Node<T> *SingleLinkedList<T>::getLoopEntrance(){ Node<T> *slow = head, *fast = head; while (fast && fast->next) {  slow = slow->next;  fast = fast->next->next;  if (slow == fast)  {   break;  } } if (fast == NULL || fast->next == NULL) {  return NULL; } fast = head; while (slow != fast) {  slow = slow->next;  fast = fast->next; } return fast;}

解法如下：

设定fast和slow两个指针，初始都指向head。然后让fast每次走2步，slow每次走一步，如果发现fast和slow重合，则确定单向链表有环路了。接下来，让fast回到链表的头部，重新走，每次步长不是走2步了，而是走1步，那么当fast和slow再次相遇的结点，就是环路的入口位置了。

证明：  
当fast和slow第一次相遇的时候，slow肯定没有遍历完一次链表或刚好遍历完一次链表，而fast已经在环内循环了n圈（n>=1）。这时，假设slow走了i个结点，则fast走了2i个结点，再假设环长为C，则  
　　2i = i + nC -> i = NC

设链表长度为L，链表起点距环入口的距离为j，环入口距相遇点的距离为k，则

j + k = i = nC

j + k = (n - 1)C + C = (n - 1)C + (L - j)

j = (n - 1)C + (L - j - k)

(L - j - k)同k一样，同样为环入口点距相遇点的距离。也就是说，从链表起点到环入口点的距离等于(n - 1)环长+相遇点到入口点的距离。于是，从链表起点、相遇点分别设一指针，每次各走一步，则两指针必定相遇，且第一个相遇点即为环入口点。

#### 给我老师的人工智能教程打call！[http://blog.csdn.net/jiangjunshow][http_blog.csdn.net_jiangjunshow] ####

![这里写图片描述][SouthEast]

[http_blog.csdn.net_jiangjunshow]: https://blog.csdn.net/jiangjunshow/article/details/77338485
[SouthEast]: /images/20220422/33c5afeebb6e4c88b456ffcc7501565a.png