1、单链表中要么只有一个环,要么没有环,因为只要进入一个环就会无限循环下去,不可能存在多个环。
2、此题解法是用快慢两个指针,慢指针每次走一步,快指针每次走两步,当两指针相遇时,慢指针退回起点,俩指针都变成每次走一步,再次相遇时,便是环入口
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
auto i = head, j = head; //i慢j快
while (i && j) { //判断当两个指针都不为空时,各走一步
i = i->next;
j = j->next;
if (j) j = j->next; //判断j不为空,继续走一步
else return nullptr; //为空直接判定为无环
if (i == j) //当i和j第一次相遇,此时说明肯定存在环,下一步找环入口
{
i = head; //将i退回起点
while (i != j) //这里不必判断i或j是否为空,因为有环会无线循环下去,永不为空
{
i = i->next; //此时i和j都变成慢指针,相等即是环入口。
j = j->next;
}
return i;
}
}
return nullptr; //找不到第一个相遇点,没有环;如果有第一个相遇点那么必然有第二个相遇点
}
};