题目描述
这道题目就是给一个链表找出环的入口处,如果没有环,那么返回NULL
样例
参照书上例子
代码部分
/*
首先判断是不是空指针,然后开始设置两个快、慢指针,快指针每次走两步,慢指针每次只走一步,然后设置一个标志位isCycle,令其为2,因为我们要算出环的长度,那么环除了第一次指向头指针相遇外,其他时候相遇两次,这两次可以算出环的长度来,通过环的长度,我们让快慢指针从头指针开始,快指针走(环的长度)cycleLength步,然后慢指针和快指针走相同的步,相遇的话就是环的入口;
/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode * head)
{
if(head == nullptr) return nullptr;
ListNode *fast = head, *slow = head;
int cycleLength = 0;
int isCycle = 2;
while(isCycle && fast->next->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast) isCycle--; // 除了头指针后的第一次相遇
if(isCycle != 2) cycleLength++; // 在第二次相遇之前计算长度
}
if(isCycle==2) return nullptr; // 说明没有环,直接返回空
cycleLength -= 1;// 环的长度多加了一次
slow = head, fast = head;
for(int i=0;i<cycleLength;i++) fast = fast->next;
while(slow != fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
};