本文共 1468 字，大约阅读时间需要 4 分钟。

原题

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

解题思路

两个关键点：该链路是否为环路，如果是的话，环路起始点在哪里？ 1.判断是否有环路。用一个指针遍历结点，如果能走到头即没有回路（注意链路可能为空，所以不光要看fast->next，还要看fast是否为NULL），如果一直往下走即为有回路。 这里就会出现一个问题，有回路就会陷入死循环，解决方法就是使用快慢双指针。fast每次前进两步， slow每次前进一步，如果能相遇即为有回路，不然慢指针永远追不上快指针（起始点都一样，所以不要用while循环）。快慢指针为何一定相遇，知乎上有用户进行了解答，一下是知乎上的解释： 1：快指针与慢指针之间差一步。此时继续往后走，慢指针前进一步，快指针前进两步，两者相遇。 2：快指针与慢指针之间差两步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差一步，转化为第一种情况。 3：快指针与慢指针之间差N步。此时继续往后走，慢指针前进一步，快指针前进两步，两者之间相差(N+1-2)-> N-1步。因此，此题得证。所以快指针必然与慢指针相遇。又因为快指针速度是慢指针的两倍，所以相遇时必然只绕了一圈。

作者：知乎用户

链接：https://www.zhihu.com/question/23208893/answer/117115415 2.环路起始点在哪里。 将fast和slow的步进都设为1，这样 相遇点必然是链路入口，不然步长一样其他地方不会相遇（当然，此时fast和slow是相遇的，需要将其拉开，将fast重新指向头结点，如果slow此时也在这，那么头结点就是入口）。相遇点一定是回路入口，但是可能有人会担心，快慢指针是不是必然会相遇，有人也对此做了证明：若在头结点和相遇结点分别设一指针，同步(单步)前进，则最后一定相遇在环入口结点p。https://www.cnblogs.com/songdechiu/p/6686520.html

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {
   public:    ListNode *detectCycle(ListNode *head) {
                   ListNode *fast,*slow;   fast=slow=head;   do   {
   	   if(fast==NULL ||fast->next ==NULL )		   return nullptr ;	   fast=fast->next ->next ;	   slow=slow->next ;   }while(fast!=slow);   fast=head;   while(fast!=slow)   {
           fast=fast->next ;		slow=slow->next ;   }   return fast;    }};