A loop or cycle in a linked list happens when a node points back to a node we have already visited instead of pointing to null. If we try to traverse this list, our code will run forever in an infinite loop, freezing the program!

Let's look at how we can detect this loop easily using a simple room-and-sticky-note analogy.

Illustration of a linked list loop detected with visited sticky notes
Real-World Analogy: Leaving Sticky Notes on Doors

Imagine you are exploring a series of connected rooms (Nodes). Each room has a single door leading to the next room.

You want to check if you are walking in a circle. Here is your plan:

  • Every time you walk into a room, you put a **bright neon sticky note** on the door (we mark isTraversed = true).
  • Before you walk through any door, you check if there is already a sticky note on it.
  • If you find a sticky note, you shout: **"Loop Detected! I've been in this room before!"**
  • If you reach a dead end (a room with no door to follow, i.e., null), you know there is no loop!

Walkthrough of the Loop Detection Scenario

Let's trace how the program executes step-by-step from the entry point of a loop checking method:

Step 1: Setting up our Nodes

We create three nodes representing our list. We also deliberately point Node C back to Node B to form a cycle:

Node1 c = new Node1("Node C", null); // we will point it to B later
Node1 b = new Node1("Node B", c);
Node1 a = new Node1("Node A", b);
c.nextNode = b; // Cycle created! C -> B
Step 2: Tracking Visited Rooms

We start checking for loops starting from the head (Node A):

  • Check Node A: Is Node A visited? No (isTraversed is false). Mark Node A as visited: a.isTraversed = true. Move to Node B.
  • Check Node B: Is Node B visited? No. Mark Node B: b.isTraversed = true. Move to Node C.
  • Check Node C: Is Node C visited? No. Mark Node C: c.isTraversed = true. Move to Node C's next node: Node B.
  • Check Node B again: Is Node B visited? **Yes!** (b.isTraversed == true). A loop is detected! The program immediately returns true.

Java Implementation

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

By using a simple boolean isTraversed flag inside our list nodes, we can easily check for loop cycles in a single pass. This visited flag approach runs in O(N) time and requires minimal extra code to implement!