LeetCode 142 环形链表 II
🟡 中等 https://leetcode.cn/problems/linked-list-cycle-ii/description/
判断有无环
设置快慢指针，while 的条件只用判断fast 和 fast->next 即可：因为 fast 一定在 slow 右侧。
/**
* 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* slow = head;
ListNode* fast = head;
bool flag = false;
while(fast&&fast->next){
slow = slow->next;
fast = fast->next->next;
if(fast==slow){
flag = true;
break;
}
}
}
};
计算入口
F：快节点路程
S：慢节点路程
b：环的长度
F = S+nb
F = 2S
可得：S = nb
又：设入口距离为 a
则当某一节点路程为 a+nb 时，该节点一定位于入口处。
因此 令fast为head， slow不变，两个重新一起走，最后一定在入口处相遇。
/**
* 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* slow = head;
ListNode* fast = head;
bool flag = false;
while(fast&&fast->next){
slow = slow->next;
fast = fast->next->next;
if(fast==slow){
flag = true;
break;
}
}
int pos = 0;
if(!flag){
return nullptr;
}else{
fast = head;
while(fast!=slow){
pos++;
fast = fast->next;
slow = slow->next;
}
return fast;
}
}
};