Floyd’s Cycle-Finding Algorithm

If you want to check if your linked list is circular you can use  Floyd’s Cycle-Finding Algorithm aka Tortoise and the Hare Algorithm.

It’s quite efficient as It has O(n) complexity.

struct Node {
  int data;
  Node* next;
}

bool hasLoop(Node* startNode) {
  // Init start settings
  Node* slowNode = startNode;
  Node* fastNode = startNode->next;

  // Search until we reached end of linked list of find cycle
  while (true) {
    if (fastNode == NULL || fastNode->next == NULL)
      return false;
    // if fastNode or it's successor reaches slowNode 
    // we have a circular list
    else if (slowNode == fastNode || slowNode == fastNode->next) 
      return true;
    slowNode = slowNode->next;
    fastNode = fastNode->next->next;
  }
}

Leave a Reply

Your email address will not be published. Required fields are marked *