Description
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
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.
Note: Do not modify the linked list.
Answer
The main idea of this problem is basically the same as Linked List Cycle. If a cycle is found, then start the faster pointer from the beginning, set the speed as the same as the slow pointer and then continue iterating. The meeting point of new start pointer and the slow pointer is the start point of the cycle.
Time Complexity
O(n) with n as the number of nodes in the input.
Code
C++
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head) return NULL;
ListNode* fast = head;
ListNode* slow = head;
int isCycle = 0;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(!fast) return NULL;
if(slow == fast) {
isCycle = 1;
break;
}
}
if(isCycle == 0) return NULL;
slow = head;
while(fast != slow)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
};
