AcWing 34. 链表中环的入口结点
原题链接
中等
作者:
qing123
,
2021-09-27 23:30:23
,
所有人可见
,
阅读 219
/**
* 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) {
if(!head||!head->next) return 0; //判断是换是否是空的
ListNode *first=head,*second=head;//从同开始进行以不同的速度
while(first&&second)
{
first=first->next;
second=second->next;
//second走两步
if(second)second=second->next;
else return 0;
if(first==second)//找到第一个相遇点
{
first=head;
while(first!=second)
{
first=first->next;
second=second->next;
}
return first;
}
}
return 0;
}
};