解法1:
需要用到额外的空间,使用set
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL)return false;//去除捣蛋的部分
//使用set解决
unordered_set<ListNode*> st;
ListNode* p = head;
bool res = false;
//将结点的地址都存入集合中
while(p){
if(st.find(p) != st.end()){
//如果该节点存在,说明这个结点就是入环节点了
res = true;
break;
}
//如果不存在该节点,需要将其放进集合中
st.insert(p);
p = p->next;
}
return res;
}
};
解法2:
空间负载度O(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) {
if(head == NULL)return NULL;//去除捣蛋的部分
//需要用到快慢指针
ListNode* low = head;
ListNode* fast = head;
bool res = false;//用来判定是否有环
while(fast != NULL){
low = low->next;
if(fast->next == NULL){
//说明此链表无环
return NULL;
}
fast = fast->next->next;
if(fast == low){
//说明有环
ListNode* ptr = head;
while(ptr != low){
low = low->next;
ptr = ptr->next;
}
return ptr;
}
}
return NULL;
}
};
cs