Solution: Re-Searching Seen Items

As with the previous problem, let’s start by placing the boilerplate code for traversing the list:

public static boolean hasCycle(ListItem head) {
  ListItem current = head;
  while (current != null) {
    // Check for cycle here
    current = current.next;
  }
  return false;  // No cycle found
}

Now we can traverse every item in the list. How do we know if the list has a cycle? Suppose you are hiking in a forest, and you want to know if you are going in circles. The clearest sign is seeing a landmark that you have already seen before. The same idea applies here.

We traverse every item in the list, and as we move from one item to the next, we expect to see new items each time. If we land on an item we have already seen, then we know we are going in circles. This is not about values. We never said that the values in the list are unique. Here is a list with all duplicates but no cycle:

          ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 1 │ ──▶ │ 1 │ ──▶ │ 1 │ ──▶ │ 1 │ ──▶ null
          └───┘     └───┘     └───┘     └───┘

And here is a list with all duplicates and a cycle:

          ┌───┐     ┌───┐
head ───▶ │ 1 │ ──▶ │ 1 │
          └───┘     └───┘
            ▲         │
            │         ▼
          ┌───┐     ┌───┐
          │ 1 │ ◀── │ 1 │
          └───┘     └───┘

So what we are tracking is an item’s identity, not its value.

So now the question is: how do we keep track of the items we have seen before?

The most direct answer is to store them. As we traverse the list, we check whether the current item is already in a collection of previously visited items. If it is, we have reached the same object twice, so there is a cycle. Otherwise, we add it to the collection and move on. This works, and it is simple. But the collection costs us memory. It holds up to one reference per item in the list, so it is $O(n)$ auxiliary space, and the problem asked for $O(1)$.

Another thing we could do is mark the items as we visit them. That would be a good strategy if you were lost in a forest: you tie a ribbon on each tree you pass, and a tree that already has a ribbon tells you that you have been here. In our case, we could change the value of each item to something that means “seen.” But our ListItem has nowhere to put a mark except the value field. So marking means overwriting the data, and the caller gets back a list with the original values gone.

So we cannot store the seen items, and we cannot mark them. What is left is to search again for what we have seen, by traversing the list again from the head. Suppose our current item is at position $i$, counting from the head. If our current item is one we have already visited, then it must be one of the items at positions $0$ through $i-1$. So we start a second traversal at the head, take $i$ steps, and compare each item we pass against current with ==. If any of them is the same object, there is a cycle. If none of them is, we take one more step with current and repeat.

The inner traversal must check only the first $i$ items, at positions $0$ through $i-1$. These are the items we have already visited. If we continue to position $i$, we reach current itself, so the identity check would report a cycle even in a list with no cycle.

$O(n^2)$ is a high cost for checking whether the list has a cycle. The cost is that high because each inner traversal starts over at the head and checks items we have already checked on the previous passes.