本题理解实现思路后,代码实现比较容易,其实现式子为2(a+b)=a+(b+c)n (n为闭环的圈数,这个式子就是快点的等式,左边是慢节点两倍,右边就是快点走的路),
可以得到,从相遇点到闭环起始点距离c与a是相等的,所以再用快指向头结点,从新遍历并将速度改为1步,当两点再次相遇时,那个点就是闭环起点。
int flag=0;//设置标志位,来改变快慢指针的状态。
if(pHead==NULL)
return NULL;
struct ListNode*slow=pHead->next;
if(slow==NULL)
return NULL;
struct ListNode* fast=slow->next;
while(fast!=NULL&&fast->next!=NULL)
{
if(fast==slow)//当快慢指针第一次遇见前,执行快走2步,慢走1步,遇到后,将快指向头,并将其步数改为1步,后面两者再次相遇点就是结点处。
{
if(flag)
return fast;
fast=pHead;
flag=1;
}
else
{
if(flag)
{
slow=slow->next;
fast=fast->next;
}
else
{
slow=slow->next;
fast=fast->next->next;
}
}
}
return NULL;
}