LeetCode 142. 【双指针】找到环的入口
原题链接
简单
作者:
大明湖的鱼
,
2021-01-06 00:05:22
,
所有人可见
,
阅读 256
注意相遇点不一定是起点,只是环内的某一点,此时让一个指针从链表头开始,都以pace =1 移动,再次相遇的点即为环的起点
/**
* 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 *dumpy = new ListNode(-1);
dumpy->next = head;
if(head == nullptr) return nullptr;
ListNode *fast = head;
bool hasCycle = false;
while(head){
head = head->next;
if(fast == nullptr || fast->next == nullptr);
else {
fast = fast->next->next;
if(head == fast) {
hasCycle = true;
break;
}
}
}
if(hasCycle){
ListNode *p = dumpy->next;
while(p != head){
p = p->next;
head = head->next;
}
return head;
}
else return nullptr;
}
};