141.环形链表 & 142.环形链表II
141.环形链表 & 142.环形链表II141.环形链表
思路：快慢指针 or 哈希表
快慢指针代码：
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head==nullptr||head->next==nullptr)
return false;
ListNode *fast=head->next; //不能设置成head，否则不进入while循环
ListNode *slow=head;
while(fast!=slow){
//如果无环fast在slow前面，只需要判断fast
if(fast->next!=nullptr&&fast->next->next!=nullptr){
fast=fast->next->next;
slow=slow->next;
}else{//无环
return false;
}
}
return true;
}
};
哈希表代码：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
unordered_set<ListNode*> hash;
ListNode* cur=head;
while(cur!=nullptr){
//哈希表中出现过
if(hash.count(cur)){
return cur;
}
hash.insert(cur);
cur=cur->next;
}
return nullptr;
}
};
142.环形链表II
思路：快慢指针+数学推导 or 哈希表
哈希表同前，数学推导见下图，
https://i-blog.csdnimg.cn/direct/f157a5a45b9940fb81442c13c1c20d8d.png
代码：
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) {
return nullptr;
}
fast = fast->next->next;
if (fast == slow) {
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return nullptr;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]