原题链接:142. 环形链表 II
solution: 用哈希表存储
/**
* 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) {
unordered_set map;
ListNode *cur = head;
while(cur != nullptr){
map.insert(cur);
cur = cur->next;
if(map.count(cur)){ //如果已经存在,则break;
break;
}
}
return cur;
}
};
双指针:如果没有环,返回nullptr;
如果有环,快慢指针一定会相遇,假设快指针一次走2步,满指针一次走1步,相遇的时候慢指针走了s步,快指针走了f = 2s步,并且f = s + nb,其中n是圈数,b是环的长度。可以解出来,s = nb; 假设head到第一个入环点的距离为a,则慢指针再走a步就到了入环点。
/**
* 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) {
if(head == nullptr) return nullptr;
ListNode *fast = head;
ListNode *slow = head;
while(fast->next != nullptr && fast->next->next != nullptr){
fast = fast->next->next;
slow = slow->next; //快指针每次走2步
if(fast == slow){
ListNode *cur = head;
while(cur != slow){
cur = cur->next;
slow = slow->next;
}
return cur;
}
}
//跳出while循环肯定没有环
return nullptr;
}
};
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)