Description
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Answer
The main idea of this problem is using two pointers with different speed to find if two pointers will meet. If the given linked list has a cycle in it, then return true . If one of the two pointers reach the edge(NULL) then return false.
Time Complexity
The complexity of each method is both O(n) with n as the length of the given linked list.
Code
C++
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head) return false;
ListNode* slow = head;
ListNode* fast = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(fast == nullptr) return false;
if(fast == slow) return true;
}
return false;
}
};
