[Amazon] Cycle in a Linked List!!

Background

One of my subordinates applied for a job at Amazon, Hyderabad and he got a call for telephonic interview. According to him, Telephonic interview of Amazon is quiet easy where they do not look for depth in a particular technology. They rather cover Operating Systems, Databases, Web Technologies, OOPs and see the breadth of knowledge a candidate has. He requested me to allow him to give my name as one of the references in his resume and I agreed on one condition; If he can share his interview experience with me. I got two questions from him, One of them is this one.

Problem Statement

You are given a singly linked list, You have to write a function which takes as an input parameter pointer to the head node of the linked list and returns boolean result based on If list has a cycle (means end node doesn't have null in it and rather points to a node in the list itself) in it or not.

Solution

First of all whenever you are asked to write a function, what you should initially do is write the function prototype and ask your interviewer if that is what he wants!! Once you get the buy-in from him, proceed further to device an algorithm.

  
  bool HasCycle(Node *head);  

Proceeding further with this function definition, let use write code for the function.

Algorithm - Let us assume we are two people and there are set of connected rooms. We need to find whether these rooms are connected in a fashion that forms cycle or not? Here assumption is we are considering rooms to be arranged like linked list.

Now when we are two persons there to find that out, Let us assume it is you and me. Now you ask me to walk faster and see if there is any room that has no exit. And you keep coming slower. If I find a dead end I will come back and report to you otherwise, there will be time, where I will be chasing you inspite of leading you, If there is a cycle it will happen for sure. Thus If I catch you while following you, We conclude that there is a cycle.

With this algorithm in place, we are ready to go and write the code. Of course, using two pointers - You and ME!!

  
  typedef struct _Node
  {
     int data;
     struct _Node* next;
  }Node;

  bool HasCycle(Node *head)
  {
     Node* fast, slow;

     fast = slow = head;

     while(true)
     {
         if(fast == NULL  fast->next == NULL)
             return false;
         else if(fast==slow  fast->next == slow)
             return true;
         else
         {
             fast = fast->next->next;
             slow = slow->next;
         }
     }
  }
  

You can easily trace this function. And Yeah!! Good Luck for your upcoming Interview!!