Description:
https://leetcode.com/problems/linked-list-cycle/#/description
https://leetcode.com/problems/linked-list-cycle-ii/#/description
Algorithm:
My solution:
As shown in Code1, set the node value to INT_MIN, and keep checking. If a INT_MIN is found, we consider we find a cycle. (kind of cheating…but passed the test cases…)
Official solution:
As shown in Code2, approach2 in https://leetcode.com/articles/linked-list-cycle/ is really amazing!
Code1:
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode *node = head;
while(node != NULL)
{
if (node->val == INT_MIN)
return true; // For 142, return node;
node ->val = INT_MIN;
node = node -> next;
}
return false; // For 142, return NULL;
}
};
Code2 (for 141):
public boolean hasCycle(ListNode head) {
if (head == null || head.next == null) {
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast) {
if (fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
Code2 (for 142):
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head || !head->next)return NULL;
ListNode*hare,*tor;
tor=head;
hare=head;
while(hare && hare->next){
tor=tor->next;
hare=hare->next->next;
if(hare==tor)break;
}
if(!hare || !hare->next )return NULL;
tor=head;
while(tor!=hare){
tor=tor->next;
hare=hare->next;
}
return tor;
}
};
Timing & space:
O(n) & O(1)
This is the fastest problem I finished. Only 3 mins are spent:)