If you've spent any time preparing for technical interviews, you've probably seen this one. Detecting a cycle in a linked list is a quintessential whiteboard problem because it tests whether you can move beyond a "brute force" mindset and find an elegant way to use memory.

Now, you could just throw every node you visit into a HashSet and check if you've seen a node before. That works, but it costs you O(n) extra space. In a real production environment, if you're dealing with a massive list, that memory overhead is a non-starter. I prefer Floyd’s Cycle-Finding Algorithm—the "Tortoise and the Hare"—because it solves the problem in O(1) space. The idea is simple: if there's a loop, a fast pointer will eventually lap a slow pointer.

Setting up our Node structure

I'll start with a bare-bones ListNode class. We don't need anything fancy here, just the value and the reference to the next node. I'm skipping the constructor logic for brevity since we've covered that in previous lessons.

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

Thinking through the two-pointer strategy

The logic is this: I'll create two pointers. The slow pointer moves one step at a time, and the fast pointer moves two. If the list is linear, the fast pointer will hit the end of the list (null) and we're done. If there's a cycle, they'll eventually land on the exact same node.

Here is how I'd start sketching this out on a whiteboard:

public boolean hasCycle(ListNode head) {
    if (head == null) return false;

    ListNode slow = head;
    ListNode fast = head;

    while (fast != null) {
        slow = slow.next;
        fast = fast.next.next;

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

Fixing the NullPointerException bug

Wait. I just caught a mistake I make almost every time I rush through this on a whiteboard. Look at the while condition and the line fast = fast.next.next;.

If fast is not null, but fast.next IS null, then calling fast.next.next will throw a NullPointerException. The fast pointer is leaping two steps, so I have to ensure that both the current node and the immediate next node are valid before I try to jump. It's a small detail, but it's the difference between a successful interview and a failed one.

Let's tighten that loop condition:

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

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

Seeing it in action

To actually test this, we have to manually create a cycle. You can't do this with a simple loop; you have to explicitly point the last node back to an earlier one. I'll create a four-node list and point the tail back to the second node.

public static void main(String[] args) {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    
    // Create a cycle: 4 -> 2
    head.next.next.next.next = head.next;

    Solution sol = new Solution();
    System.out.println("Cycle detected: " + sol.hasCycle(head)); 
    // This should print true
}

The beauty here is that we didn't store a single extra reference outside of our two pointers. No matter how long the list is, the memory footprint remains constant.

📋 Practical Task

Exercise: Validating a Circular Undo-History Buffer

In some text editors, the "undo" history is stored in a linked list. To prevent the history from growing infinitely, some systems implement a circular buffer where the oldest history node is eventually overwritten or linked back to a previous state to create a loop.

Your task is to implement a method called isHistoryCircular(ListNode head). This method should return true if the undo-history has formed a cycle and false if it is a standard linear list.

Requirements:

• Implement the logic using the "Tortoise and Hare" approach.
• Ensure your code handles empty lists (null head) and lists with only one node without crashing.
• The solution must operate with O(1) auxiliary space complexity.