How to Detect a Cycle in a Linked List
Tags: algorithms, datastructures, computerscience, codinginterviews
Published: 2023-02-11 21:21:44

When developing [Cyclone Scheme](https://github.com/justinethier/cyclone) I discovered the latest [R<sup>7</sup>RS](https://small.r7rs.org/attachment/r7rs.pdf) 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](https://en.wikipedia.org/wiki/Cycle_detection):

> 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`:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/owliqe1uqvzrkem0czw6.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/05vshxw8cv4vvoaa438g.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o41x0dnth8go0auuaov5.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/nxnesb4eb6d5kxjxzpii.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j8d00gpt7ijs4n3gqlhs.png)

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:

```javascript
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:

```javascript
/**
 * @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:

```c
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](https://github.com/justinethier/cyclone/blob/bde930a18b1aed12dc833c605d5cec1738d65559/runtime.c#L917) 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](https://leetcode.com/problems/linked-list-cycle/) interview question.