Given a linked list, check if it has a cycle in it, solution in C++

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

List Of Tutorials available in this website: