How to check if a linked list is cyclic or not

It is a regular interview question: given a one - direction linked list, how to check if there is a cycle inside the list or not.

As usual, you will receive a pointer to the head of the list, and you write a function to return a Boolean value which indicates there is a cycle inside the list or not.

The obvious way is creating another list / array to store all the elements of the list you visited, but in some cases it is not possible.

You can always use this approach, even in the case the node element has no data but a pointer to the next one. If so, you can just store the pointer (i.e, the address).

But of course it is not the intention of the interview. If the interviewer asked you to write an algorithm with time complexity is O(n) or space complexity is O(1), the above approach is not suitable.

There is a better algorithm: using two pointers, one fast and one slow. Slow pointer moves one element per iteration, while fast pointer moves two. If they meet, it means there is a cycle, and if fast pointer meets NULL, means no cycle.

You can check my implementation (in C++) at: http://pastebin.com/bRfYhBBD or check the following code:

#include 
#include 

typedef struct Node {
 Node* next;
} Node;

bool checkCylic (Node* head) {
 Node* slow = head;
 Node* fast = head;
 if (head == NULL) return true;
 while (fast->next != NULL) {
  slow = slow->next;
  fast = fast->next;
  if (fast->next != NULL) {
   fast = fast->next;
  } else return false;
  if (fast == slow) return true;
 }
 return false;
}

int main () 
{
 Node head1, node1;
 head1.next = &node1;
 node1.next = NULL;

 Node head2, node2, node3, node4;
 head2.next = &node2;
 node2.next = &node3;
 node3.next = &node4;
 node4.next = &node3;

 assert (checkCylic(&head1) == false);
 assert (checkCylic(&head2) == true);

 return 0;
}