In the previous question, we wanted to know if there is a cycle. But in this question we want to know the node from where the cycle begins.
For example:
1 -> 2 -> 3 ->4 ->3 Entrance of the cycle is 3.
The steps are given below:
- Take 2 pointers, “slow” and “fast”
- Fast moves 2 steps and slow will move 1 step at a time
- If both “fast” and “slow” meet at a point, there is a cycle.
- Then reset “slow” pointer, pointing to head.
- Then move “slow” and “fast” pointer one step at a time.
- The time they meet again is the cycle starting point.
- Return “slow” or “fast” pointer.
Solution in C++
#include<iostream> #include<vector> using namespace std; struct Node { public: int data; Node *next; Node(int x) { data = x; next = NULL; } }; Node *detectCycle(Node *head) { Node *fast = head; Node *slow = head; while (1) { if (fast==NULL||fast->next==NULL) return NULL; // this means no cycle fast=fast->next->next; slow=slow->next; // we got a cycle if (fast==slow) break; } slow = head; while (slow!=fast) { slow=slow->next; fast=fast->next; } return slow; } int main() { Node *start = new Node(1); start -> next = new Node(2); start -> next -> next = new Node(3); start -> next -> next -> next = new Node(4); start -> next -> next -> next -> next = new Node(5); //create a cycle start -> next -> next -> next -> next = start; Node *result = detectCycle(start); if( result != NULL) cout<<"The cycle starting point is "<< result->data <<endl; else cout<<"There is NO cycle in the list"<<endl; return 0; }
Output:
The cycle starting point is 1