Thursday, March 10, 2011

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.

4 comments:

  1. thank u for this code

    ReplyDelete
  2. pretty simple way to check !!

    ReplyDelete
  3. Liked your post. :) Here is my code in java as well from http://k2code.blogspot.in/2011/12/finding-start-of-loop-in-circular.html:
    /**
    * Returns the node at the start of a loop in the given circular linked
    * list. A circular list is one in which a node's next pointer points
    * to an earlier node, so as to make a loop in the linked list. For
    * instance:
    *
    * input: A -> B -> C -> D -> E -> C [the same C as earlier]
    * output: C
    *
    *
    * @param linkedList
    * list to be tested
    * @return the node at the start of the loop if there is a loop, null
    * otherwise
    */
    public static IntegerNode findLoopStart(LinkedList linkedList) {
    if (linkedList == null || linkedList.getHead() == null) {
    return null;
    }

    IntegerNode loopStartNode = null;
    IntegerNode slow = linkedList.getHead();
    IntegerNode fast = linkedList.getHead();

    while (slow != null && fast != null) {
    slow = slow.getNext();
    if (fast.getNext() == null) {
    loopStartNode = null;
    break;
    }
    fast = fast.getNext().getNext();

    // If slow and fast point to the same node, it means that the
    // linkedList contains a loop.
    if (slow == fast) {

    slow = linkedList.getHead();

    while (slow != fast) {
    // Keep incrementing the two pointers until they both
    // meet again. When this happens, both the pointers will
    // point to the beginning of the loop
    slow = slow.getNext(); // Can't be null, as we have a loop
    fast = fast.getNext(); // Can't be null, as we have a loop
    }

    loopStartNode = slow;
    break;
    }
    }

    return loopStartNode;
    }

    ReplyDelete
  4. You can find out the cycle or loop in a single linked list by using two pointer approach.
    Below link can be useful to find out the algorithm to find cycle or loop in linked list

    find out the cycle or loop in a single linked list in java

    ReplyDelete