How to Detect a Cycle in a Linked List

When developing Cyclone Scheme I discovered the latest R⁷RS Scheme language specification requires that several procedures handle circular lists.

For example when comparing objects for equality:

Even if its arguments are circular data structures, equal?
must always terminate.

We can't make a simple loop over the list because our code will keep running forever if one of the nodes points back to an earlier node.

So what to do?

Floyd's Tortoise and Hare Algorithm

Well, it turns out there is an elegantly simple solution:

Robert W. Floyd's tortoise and hare algorithm moves two pointers at different speeds through the sequence of values until they both point to equal values.

Let's demonstrate how it works.

We start with a linked list of 5 nodes, A through E. Each one is linked in alphabetical order except node E which links back to A, forming a cycle.

We will use two pointers to traverse the list. A slow pointer starting at the first node in the list, A, and a fast pointer starting at B:

Now we can make several iterations, each time advancing the slow pointer ahead one node and the fast pointer ahead by two nodes:

As you can see the fast pointer reaches E and starts back around at the front of the list. After four iterations it caches up to the slow pointer and both now point to E.

Since the pointers are moving at different speeds they can only point to the same node if there is a cycle.

A JavaScript Implementation

To implement a solution in JavaScript we start with the definition for each node in a singly-linked list:

class Node {
  constructor (val) {
     this.val = val;
     this.next = null;
  }
}

And here is our cycle detection algorithm. By having a fast and slow pointer traverse the list we can find cycles efficiently with only a small amount of code:

/**
 * @param {Node} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    if (head === null) { return false; }

    var slow = head, fast = head.next;

    while (fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) return true;
    }

    return false;    
};

There is no need to check for slow === null because fast will always reach the end of the list first.

Also, we must ensure fast.next is not null before accessing fast.next.next.

Implementation in the Cyclone Scheme Runtime

Going back to my original problem, perhaps it would be interesting to briefly discuss a real-world application of this algorithm.

In Scheme lists are a fundamental data construct similar to linked lists in other languages. Their definition as a C structure is equivalent to Node above with a value stored in pair_car and pair_cdr pointing to the next pair_type object:

typedef void *object;
typedef struct {
  ... // Omit object header fields
  object pair_car;
  object pair_cdr;
} pair_type;

For various reasons the Cyclone runtime's implementation is more complicated than the JavaScript code above. Here is Cyclone's function to determine if a list contains a cycle.

Conclusion

And there you have it. Thanks for reading!

Note this problem is also popular now as a LeetCode interview question.