The problem

I am given the head node of a linked list and I need to determine if there are any circular references.

After last problem, I'm very appreciative of an easy one. I need to go through the list, cache the nodes I've already visited, and if next is a node I've already visited, I return true, indicating that we're in a loop. If I reach the end of the list, it means next is null, at which point I can return false.

The code -

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function hasCycle(head: ListNode | null): boolean {
    const foundVals = new Set<ListNode>();
    let curr = head;
    while(true){
        if(!curr?.next){
            return false
        }
        if(foundVals.has(curr)){
            return true
        }
        foundVals.add(curr)
        curr = curr.next;
    }
}

This has an O(n) runtime complexity, but is spatially expensive due to the Set.

A review of Sets

My original solution had foundVals as a list of numbers, and instead of adding the whole node, I added node.val. This worked for most of the scenarios, but there were scenarios in which different nodes shared a value, but should still be counted differently.

I am intrigued by the magic of Sets, as it feels almost like cheating the way in which I can evaluate an entire node against a set of existing nodes.

Aha - I've learned more about Sets. This works because when added objects to Sets, they're added by reference instead of by value, so instead of evaluating the whole object, the Set.has() check is simply evaluating against locations in memory. When storing primitive values, though, they are stored by value instead of my reference.

Another possible solution

Another possible solution to this problem is to use our old friend two pointers and use Floyd's Cycle Finding Algorithm. In this algorithm, we have two pointers going through the list at different speeds. If there is a cycle, they will end up on the same node at some point before the faster node ever reaches the end of the list.

function hasCycle(head: ListNode | null): boolean {
    let slow = head;
    let fast = head;
    
    while(fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if(slow === fast) {
            return true;
        }
    }
    
    return false;
}

When I ran this on Leetcode, it was decently slower than my original solution, while still being O(n), but took up way less space! This has an O(1) space complexity, since we're not caching any values.

Final thoughts

Again, I'm grateful for an easy problem, impressed with the magic of JS Sets, and intrigued by the number of seemingly infinite on-off algorithms for specific problems. Shout out Floyd, whomever you may be.