Detecting loops inside singly linked lists is a common problem in software engineering. A loop occurs when a node's pointer links back to a previously visited node instead of pointing to null. If your traversal logic is not prepared for this, it will loop indefinitely, locking up threads and causing system crashes.

While Floyd's two-pointer algorithm is highly popular, another straightforward method is the Visited State Flag approach. By adding a simple boolean state variable to each node, we can track our traversal history directly. This article explains how this visited state approach works, its real-world analogy, and its technical trade-offs.

Illustration of a linked list loop detected with visited sticky notes
Real-World Analogy: The Maze and Neon Sticky Notes

To understand the visited flag approach, imagine exploring a maze composed of consecutive rooms. Each room has a single door leading to the next room.

To ensure you don't walk in circles, you decide to use a pack of bright neon sticky notes:

  • Every time you enter a room, you check the door.
  • If there is already a sticky note on the door, you immediately know you've been here before. You stop and declare: "Loop Detected!"
  • If the door has no sticky note, you place one on it and continue to the next room.
  • If you reach a dead end (a room with no exit door, i.e., null), you know the path is loop-free.
In code, the rooms represent Node instances, and the sticky notes represent a boolean isTraversed instance variable.

Algorithmic Logic

To implement this visited flag approach in Java:

  • We add a boolean field isTraversed to our node class.
  • When traversing the list, we iterate from node to node:
    • If we reach a node where isTraversed is already true, we immediately return true, indicating a cycle.
    • Otherwise, we set isTraversed to true and move to the next node.
  • If the traversal reaches null without encountering any marked nodes, we return false.

Step-by-Step Scenario Trace

Let's trace this walkthrough using a list: Node A → Node B → Node C → Node B (forming a cycle B → C → B):

  • Start at Node A: We check Node A's isTraversed flag. It is false. We mark it true and move to Node B.
  • Inspect Node B: We check Node B's flag. It is false. We mark it true and move to Node C.
  • Inspect Node C: We check Node C's flag. It is false. We mark it true and move to Node C's next node: Node B.
  • Inspect Node B again: We check Node B's flag. It is true! The program halts and returns true, indicating a loop.

Implementation in Java

Below is the complete Java code demonstrating how Node1 utilizes the isTraversed boolean state flag to detect a cycle:

package io.practise.accolite;
 
public class LinkedListLoopDetector {
 
    public static void main(String[] args) {
        // Construct nodes
        Node1 c = new Node1("Node C", null);
        Node1 b = new Node1("Node B", c);
        Node1 a = new Node1("Node A", b);
 
        // Point Node C back to Node B to create a loop
        c.nextNode = b; 
 
        boolean hasLoop = detectLoop(a);
        System.out.println("Does the list have a loop? " + hasLoop);
    }
 
    private static boolean detectLoop(Node1 head) {
        Node1 current = head;
        while (current != null) {
            if (current.isTraversed) {
                return true; // We hit a node we already marked! Loop found.
            }
            current.isTraversed = true; // Mark as visited (sticky note)
            current = current.getNextNode();
        }
        return false; // Reached the end (null) with no cycles
    }
}
 
class Node1 {
    String data;
    Node1 nextNode;
    boolean isTraversed;
 
    Node1(String data, Node1 nextNode) {
        this.data = data;
        this.nextNode = nextNode;
    }
 
    public String getData() {
        return data;
    }
 
    public Node1 getNextNode() {
        return nextNode;
    }
}

Conclusion & Practical Trade-offs

The visited flag approach runs in O(N) linear time complexity. Its main advantage is its simplicity and ease of debugging. However, it has key practical trade-offs:

  • Memory Overhead: Adding a boolean variable to every node increases the memory footprint, especially for large datasets.
  • Mutating State: It modifies the list's nodes. If multiple threads traverse the list simultaneously, or if you need to perform multiple traversals, you must reset the flags to false first, introducing overhead.
For stateless, read-only lists, alternative algorithms like Floyd's Cycle Detection or a separate HashSet visited log are generally preferred. Nonetheless, the visited flag method is an intuitive, easy-to-understand solution for simple pointer traversal problems.