☕ DSA Java Articles

Topics › Linked List › Medium Problems of LL

Detect a loop in LL

Medium TUF ID 2845 A2Z

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list. Normally the last node’s next is null. In this problem the last node might instead point back to some earlier node, so that following next pointers forever never reaches null. Return true if the list contains such a loop (cycle) and false otherwise.

Only the pointer structure matters. Two nodes with equal values are not a loop; a loop exists only when the same node object is reached twice. In the test harness, the loop is described by the index pos of the node the tail points to (pos = -1 means no loop), but pos is not available to the solution.

Constraints: 0 ≤ n ≤ 10^4 nodes, values fit in a 32-bit signed integer.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Example 1

head = 3 -> 2 -> 0 -> -4,  tail points to index 1 (the node 2)
answer = true                 // 3 -> 2 -> 0 -> -4 -> 2 -> 0 -> -4 -> ...

Example 2

head = 1 -> 2,  tail points to index 0
answer = true                 // the whole list is one loop

Example 3

head = 1,  no loop
answer = false                // the only node's next is null

Approach 1: Brute force, remember visited nodes

Intuition. A loop means some node is visited twice. So walk the list and record each node in a set. If the next node is already in the set, we have come round the loop; if we reach null, there was no loop. The set must store node references, not values, because distinct nodes may hold equal values.

Algorithm.

  1. Create an empty HashSet<ListNode>.
  2. Walk from head. For each node, try to add it to the set.
  3. If add returns false (the node was already present), return true.
  4. If the walk reaches null, return false.
static boolean bruteForce(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    for (ListNode t = head; t != null; t = t.next) {
        if (!seen.add(t)) return true;     // add returns false when the node object was already in the set
    }
    return false;
}

Complexity. Time O(n): every node is visited at most twice (the second visit ends the loop) and each set operation is O(1) on average. Space O(n): the set holds up to n node references.

HashSet<ListNode> works on identity here because ListNode does not override equals or hashCode, so two nodes compare equal only if they are the same object. That is exactly what we want.

The approach is correct and simple, but it uses memory proportional to the list. The question interviewers want answered is whether a loop can be detected with constant extra space.

Approach 2: Optimal, Floyd’s tortoise and hare

Intuition. Picture two runners on a track. If the track is a straight line with an end, the faster runner reaches the end first and the race is over. If the track contains a circle, both runners eventually enter the circle and run round it forever, and the faster one must at some point lap the slower one, landing on exactly the same spot. That is the whole idea: move slow one node per step and fast two nodes per step. If fast hits null, there is no loop. If slow == fast, there is.

Why must they meet exactly rather than jump over each other? Once both are on the loop, the distance from slow forward to fast (measured along the loop) shrinks by exactly one node each step, because fast gains one node per step. A gap that decreases by one each step passes through zero, and gap zero means they are on the same node. So the meeting happens within one lap of the loop after slow enters it.

Algorithm.

  1. Set slow = head and fast = head.
  2. While fast and fast.next are both non-null:
    • slow = slow.next; fast = fast.next.next.
    • If slow == fast, return true.
  3. Return false (the fast pointer ran off the end).
static boolean optimal(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;                  // one step
        fast = fast.next.next;             // two steps
        if (slow == fast) return true;     // same node object, not same value
    }
    return false;                          // fast fell off the end, so there is no loop
}

Dry run on 3 -> 2 -> 0 -> -4, tail pointing to the node 2:

step slow fast slow == fast?
0 3 3 start
1 2 0 no
2 0 2 no
3 -4 -4 yes, loop

Complexity. Time O(n): before the loop, slow needs at most n steps to enter it, and once inside the gap closes in at most one lap, so the total is linear. Space O(1): two pointers.

Checking fast != null && fast.next != null before moving is what keeps the two-step move safe; writing fast.next.next when fast.next is null would throw a NullPointerException.

The comparison slow == fast is reference equality. Comparing slow.val == fast.val would be wrong: a list such as 4 -> 4 -> 4 -> 4 -> null has no loop even though values repeat, and the tests include exactly that case.

Edge cases and pitfalls