Problem: Detect a Cycle in a Linked List

Let’s try another classic linked list problem: detecting a cycle.

What is a cycle? There is a cycle when an item in the list points back to an earlier item. If you keep following next from there, you go around in a loop. We saw one earlier in this chapter. We set head.next.next.next.next = head, so the last item pointed back to the head and the list became a circular linked list.

          ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 8 │ ──▶ │ 7 │ ──▶ │ 5 │ ──▶ │ 9 │ ──┐
          └───┘     └───┘     └───┘     └───┘   │
            ▲                                   │
            └───────────────────────────────────┘

Now this problem is more general. An item could point back to any previous item, not just the head.

          ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 8 │ ──▶ │ 7 │ ──▶ │ 5 │ ──▶ │ 9 │ ──┐
          └───┘     └───┘     └───┘     └───┘   │
                      ▲                         │
                      └─────────────────────────┘

The signature of the method in Java might look like this:

public static boolean hasCycle(ListItem head) {
  // Your implementation goes here
}

Here ListItem is the class we defined earlier in this chapter.

This problem usually comes with a constraint: solve it with auxiliary space. That means we can use only a constant number of extra references. We cannot keep a collection of the items we have visited. It also usually requires a single pass through the list.

Let’s think of some special or edge cases as well:

  • If the input list is empty (i.e., head is null), there cannot be a cycle, so the method should return false.
  • If the list is a linear list with no cycles, the method should return false.
  • If the list has just one item, that item could point to itself. That is a cycle, so the method should return true.

We saw a case where the cycle points back to the head, and another case where it points back to a middle item. For this problem, we do not worry about a cycle that we would never reach by starting at head. As we follow next references, one of two things happens. Either we eventually reach null, or we eventually revisit an item we have already seen. Once we revisit an item, the traversal is inside a cycle and will keep looping.

          ┌───┐     ┌───┐
head ───▶ │ 8 │ ──▶ │ 7 │
          └───┘     └───┘
            ▲         │
            │         ▼
          ┌───┐     ┌───┐
          │ 9 │ ◀── │ 5 │
          └───┘     └───┘