Necessary and Sufficient

Problem: You have a singularly-linked list that has a cycle in it. Define an algorithm that proves that the list has a cycle. Your algorithm must have linear time complexity and cannot mark the list items.

Solution: A linked list with a cycle in it means that when you start traversing the list you will eventually retrace your steps and enter an infinite loop.

One way to detect a cycle is by keeping track of nodes already visited in the list, but the question prohibits us from marking the elements or using an additional data structure. In fact, even if the question allowed us to use an alternate data structure it would not be efficient to have to search an auxiliary "visited" list on each node.

Another way to detect the cycle is to use 2 pointers - one that advances one step at a time and one that advances 2 steps at a time. If either pointer runs into a NULL node then we know the list does not have a cycle. And because the faster pointer steps ahead 2 nodes at a time it will eventually catch/overtake the slower pointer. We can use this fact to detect the loop and break out of the infinite loop.

This technique is known as Floyd's cycle-finding algorithm, or the "tortoise and hare" algorithm. It has linear run time complexity and constant space complexity.

Here's my C++ code to do it.

   1:  #include <stdio.h>

   2:  #include <stdafx.h>

   3:  #include <malloc.h>

   4:   

   5:  struct node{

   6:      int data;

   7:      node* next;

   8:  };

   9:   

  10:  void push(node** head, int data){

  11:      node* newNode = new node;    // struct keyword not necessary in C++

  12:      newNode->data = data;

  13:      newNode->next = *head;

  14:      *head = newNode;

  15:  }

  16:   

  17:  bool detectCycle(node* head){

  18:      node* fast = head;

  19:      node* slow = head;

  20:   

  21:      do{

  22:          if (fast->next == NULL || fast->next->next == NULL)

  23:              return false;

  24:   

  25:          fast = fast->next->next;

  26:          slow = slow->next;

  27:      } while(fast != slow);

  28:      return true;

  29:  }

  30:   

  31:  int main(){

  32:      

  33:      node* head= NULL;        

  34:      for(int i=7; i>=1;i--){

  35:          push(&head, i);

  36:      }

  37:      

  38:      // close the list

  39:      node* last = head;

  40:      while(last->next != NULL){

  41:          last = last->next;

  42:      }

  43:      last->next = head;

  44:   

  45:      bool hasCycle = detectCycle(head);

  46:      printf("hasCycle= %d\n",hasCycle);

  47:  }