Algorithm to determine if a linked list is circular or has a loop

Problem: how do you find out if a linked list is circular (ie. 1->2->3->4->1) or has a loop (ie. 1->2->3->4->2)?

Understand the problem: a circular linked is like a circle where the end node points to the head node instead of null like in a regular linked list. The example, 1->2->3->4->1, has the end node 4 points to the head node 1, creating a cycle. Similarly, a linked list is said to have a loop when it contains a cycle. However, the cycle doesn't have to start at the head node. It can start at any node in the list. For instance, 1->2->3->4->2 has a loop that starts at node 2 and ends at node 4.

Solution: to solve this problem, we'll have two pointers moving at different speeds over the list. The slow pointer will move through the list one one at a time while the fast pointer will move over two nodes at a time. In other words, the fast pointer will move twice as fast as the slow pointer. When the slow and fast pointer point at the same node, we know that the linked list either is circular or has a loop. But if the linked list is just a regular list, the fast pointer will reach null before the slow pointer.

Algorithm implementation: here is the algorithm implemented in C++

#include<iostream>
using namespace std;

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

bool hasLoopInList(Node* head)
{
  if (head == NULL)
    return false;

  Node* slow = head;
  Node* fast = head;

  while (fast->next != NULL && fast->next->next != NULL)
  {
    slow = slow->next;
    fast = fast->next->next;

    if (slow == fast)
      return true;
  }

  return false;
}

Code explanation:

1. Check whether the list is empty. If it is, return false because an empty list neither is circular nor has loop.
2. Create two pointers, slow and fast, that are used to traverse the list and determine if the list has loop or not. Initially, these pointers will point at the first node in the list.
3. Next, we just need to loop until our fast pointer reaches null or until the slow and fast pointer points at the same node. If the list is just a regular list, nothing will happen inside the while loop. And, the while loop will end eventually because the fast pointer will reach null. On the other hand, if the list has loop or is circular, the slow and fast pointers will eventually point at the same node. That's why we check for that condition for every iteration of the while loop. And as soon as we know the list has a loop, we return true.

This is a very efficient way to find out if a linked list has loop or is circular. The time complexity is O(n) where n is the number of nodes in the list. Moreover, the space complexity is O(1) because we only need two pointers no matter how long the list we need to check is.