Solution Explanation:
Take an extra pointer “fast” and assign its starting point to head.
Every iteration moves the “fast” pointer 2 steps forward and “head” pointer 1 step forward.
At certain point, if there is a cycle, both “head” and “fast” pointer will meet at the same location.
Note: By this method, we loose the head pointer. To retain the head pointer, copy the head pointer address to a separate temp variable and restore the head pointer after the calculation has been completed.
Solution in C++
#include<iostream> #include<vector> using namespace std; struct Node { public: int data; Node *next; Node(int x) { data = x; next = NULL; } }; bool hasCycle(Node *head) { Node *fast; fast = head; while (head) { head = head->next; if (fast->next && fast->next->next) fast = fast->next->next; else return false; if (fast == head) return true; } return false; } 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; if(hasCycle(start)) cout<<"There is a cycle in the list"<<endl; else cout<<"There is NO cycle in the list"<<endl; return 0; }
Output:
There is a cycle in the list