Given a linked list, determine if it has a cycle in it.

Follow up:

Can you solve it without using extra space?

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++

/*
* File     : ckeck_cycle_in_list.cpp
*/

#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