Linked List Cycle Detection

Google

Linked List

Two Pointers

Given the head of a linked list, determine if the linked list has a cycle in it.

A cycle exists if some node in the list can be reached again by continuously following the next pointer. Return true if there is a cycle, false otherwise.

Solution Walkthrough

This is the classic "tortoise and hare" problem, solved elegantly with Floyd's Cycle Detection Algorithm using two pointers moving at different speeds.

Initialize a slow pointer and a fast pointer, both starting at head.
On each step, move slow forward by one node and fast forward by two nodes.
If the list has no cycle, fast (or fast.next) will eventually hit null — return false.
If the list does have a cycle, fast will eventually "lap" slow and they will point to the same node — return true.

Because the gap between the two pointers shrinks by one node every step once both are inside the cycle, they are guaranteed to meet. This runs in O(n) time with O(1) extra space — no visited-set required.

function hasCycle(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            return true; // pointers met -> cycle found
        }
    }

    return false; // fast reached the end -> no cycle
}

Related Algorithms

Singly Linked List →