Topics › Linked List › Medium Problems of LL

Detect a loop in LL

Medium TUF ID 620 SDEBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

You are given the head of a singly linked list. Return true if the list contains a loop, meaning that by following next pointers from the head you eventually come back to a node you have already visited. Return false if the walk reaches null.

When a loop exists, the list never ends, so “walk until null” never terminates. The whole problem is about detecting that situation in finite time. Test harnesses usually describe the loop with an index pos: the last node’s next points to the node at index pos, and pos = -1 means no loop. The method itself only receives head.

Constraints: up to 10^4 nodes in the LeetCode version. The follow-up asks for O(1) extra memory.

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

Example 1

3 -> 2 -> 0 -> -4
     ^          |
     +----------+          // pos = 1: the last node points back to the node holding 2
answer = true

Example 2

1 -> 2 -> 3 -> 4 -> 5 -> null
answer = false             // the walk reaches null

Example 3

7 -> (back to 7)           // a single node whose next is itself
answer = true

Approach 1: Brute force, remember every visited node

Intuition. In a list without a loop, a walk from the head visits every node exactly once and then hits null. In a list with a loop, the walk must eventually step onto a node it has already seen, because there are only finitely many nodes. So we record every node we pass in a hash set; the first time we try to record a node that is already there, we have proof of a loop.

Algorithm.

1. Create an empty HashSet<ListNode>.
2. Walk the list. For each node, try to add it to the set. If add returns false, the node was already present: return true.
3. If the walk reaches null, return false.

static boolean hashing(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    for (ListNode cur = head; cur != null; cur = cur.next) {
        if (!visited.add(cur)) return true;         // add() is false when this node object was seen before
    }
    return false;                                   // reached null, so the list ends
}

Complexity. Time O(n): each node is added once, and the walk stops at the first repeated node, which happens within n + 1 steps. Space O(n) for the set.

HashSet.add returns false when the element is already present, which saves a separate contains call. Because ListNode does not override equals, the set compares nodes by identity. Storing values instead (Set<Integer>) would be a bug: 1 -> 1 -> 1 has repeated values but no loop.

Approach 2: Optimal, Floyd’s tortoise and hare

Intuition. Put two pointers on the head. The tortoise (slow) moves one node per step, the hare (fast) moves two.

• If there is no loop, the hare is always ahead and reaches null first. We stop and answer false.
• If there is a loop, the hare enters it first and runs around it forever. The tortoise eventually enters too. From that moment both pointers are on the same circle, and the hare is some distance d behind the tortoise (measured in the direction of travel). Every step the hare gains exactly one node, so d becomes d - 1, then d - 2, and so on. A distance that shrinks by exactly one cannot skip over zero, so after at most C steps (the loop length) the two pointers stand on the same node.

That last argument is also why the speeds are 1 and 2. With speeds 1 and 3 the gap shrinks by two per step, and on a loop of even length an odd gap would never reach zero.

Algorithm.

1. Set slow = head and fast = head.
2. While fast != null and fast.next != null:
   • slow = slow.next, fast = fast.next.next.
   • If slow == fast, return true.
3. Return false.

static boolean optimal(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;                           // 1 step
        fast = fast.next.next;                      // 2 steps
        if (slow == fast) return true;              // the hare caught the tortoise inside the loop
    }
    return false;                                   // the hare found the end of the list
}

Dry run on Example 1. Name the nodes by index: n0 = 3, n1 = 2, n2 = 0, n3 = -4, with n3.next = n1.

On Example 2 the hare visits 1, 3, 5 and then finds fast.next == null, so the loop exits after two steps and returns false.

Complexity. Time O(n): if there is no loop the hare reaches the end in about n / 2 steps; if there is a loop of length C after a tail of length L, the tortoise enters the loop after L steps and is caught within C more, and L + C ≤ n. Space O(1): two pointers.

The order of the loop condition matters. fast != null must be tested before fast.next != null, otherwise an even-length list throws a NullPointerException on its last step. The check slow == fast is placed after moving; checking before the first move would report a loop immediately because both start on the head.

Edge cases and pitfalls

• Empty list. head == null fails the loop condition at once and returns false. The hash set version also returns false.
• Single node. Without a loop, fast.next == null ends the loop. With a self-loop (head.next == head), after one step slow and fast are both on head, so the answer is true.
• Loop through the whole list. When the last node points back to the head there is no tail at all; the argument above still holds with L = 0.
• Values are irrelevant. Repeated values do not imply a loop. Compare node references, as both methods do.
• Do not modify the list. Tricks such as overwriting values with a sentinel, or pointing every visited node at a dummy, also detect loops in O(1) space but destroy the input. Interviewers usually reject them.
• Long lists. The Java tests include lists of 10^5 nodes, with no loop, with a self-loop at the very end, and with one giant loop, to show that both methods stay linear.

Related problems

• Detect a loop in LL is the same problem in the A2Z sheet.
• Find the starting point in LL extends Floyd’s algorithm to locate the node where the loop begins.
• Length of loop in LL keeps one pointer still after the meeting and counts the steps around the loop.
• Find the Duplicate Number applies the same tortoise and hare idea to an array viewed as a linked list.
• Find the intersection point of Y LL is another list problem decided by node identity rather than values.