Find a cycle in the linked list OR Find out if the linked list is cyclic or not

It is a very common question in the interviews. Most times it is asked during white board interviews but sometimes it can be asked during phone interviews.

Following diagram is a linked list without cycle:



Following diagram is a Linked list with cycle:


To find a cycle in the linked list, we will use two pointers. Pointer first and second. In the first iteration, first pointer will point to the next. Second pointer will point to first's next. Following diagram demonstrates this:


After first iteration, first pointer will point to second node, and second pointer will point to second->next->next. Since it contains 3 nodes, after first iteration both the first and second pointer will point to the second node.



Algorithm:

1. Initialize two pointers first and second. First will point to head, second will point to first->next
2. Increment pointer first to first->next and second to second->next->next.
3. Repeat step 2 till second pointer reaches null or meets the first pointer

Complexity:
Time complexity: It will be O(n) since it will traverse through n nodes to find the cycle or reach the cycle's end.

Space complexity: It will be O(1) since constant space is required during algorithm execution.

Implementation:

 
int find_cycle()
{
 node *first, *second;
 first = head;
 second = head;

 //Moving one pointer at the speed of 1 and other at the speed of 2
 while(second->link!=NULL)
 {
  first = first->link;
  second = second->link->link;

  if(first->data == second->data)
  {
   std::cout<<"\nCycle present\t"<link == NULL)
   return NULL;
 }

 //Detecting the start of the cycle.
 first = head;
 while(first!=second)
 {
  first = first->link;
  second = second->link;
 }

 std::cout<<"\nCycle present at:"<data<<"\n";
}

You might also like:

Find White Spaces in Character Array

Find a character in the String

Number is prime or not

Finding Absolute Value

Notes on Sorting and Searching Algorithms

Common String Functions

Reverse a String

Product of all array location expect its own

Find a binomial co-efficient

Remove duplicates from the array

Telephonic phone technical interview questions

Telephonic phone technical interview questions - Part 2

Counting sort algorithm

B-Tree