Linked List Cycle

You are given head, the first node of a singly linked list. Normally the last node's next is null, but in this list the last node might instead point back to some earlier node (or to itself), creating a loop that never ends.

Return true if following next pointers from head ever revisits a node, and false if the walk reaches null.

In the examples the list is described as {"values": [...], "pos": k}: the node values from the head onward, and the index the last node links back to (-1 for no loop). Your function only receives head, not pos. Values may repeat, so a value seen twice does not prove a loop.

Example 1

Example 2

Example 3

Constraints

• 0 <= number of nodes <= 104
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the list.

Pattern Path · Linked Lists · problem 67 of 169

Start simple

Walk the list and store every visited node in a hash set, reporting a loop when a node is seen twice: O(n) time but O(n) extra space.

The key idea

Use two pointers that start at head: slow moves one node per step and fast moves two. This is often called Floyd's tortoise-and-hare technique.

If there is no loop, fast runs off the end of the list (it or its next becomes null), and you return false.

If there is a loop, both pointers eventually enter it and then keep circling. From that moment, every step brings fast exactly one node closer to slow along the loop, because it moves one node more per step. The gap therefore shrinks by one each step and must hit zero: the pointers land on the same node, and you return true. Fast cannot jump over slow, since the gap goes down one at a time.

Compare node identity, not values, because values can repeat. The slow pointer covers at most the list length before they meet, so the time is linear, and only two pointers are stored.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def hasCycle(self, head):
        slow = fast = head
        while fast and fast.next:
            slow = slow.next       # one step
            fast = fast.next.next  # two steps
            if slow is fast:       # same node object, not just the same value
                return True
        return False               # fast reached the end, so there is no loop

JavaScript

var hasCycle = function(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;       // one step
    fast = fast.next.next;  // two steps
    if (slow === fast) return true; // same node object, not just the same value
  }
  return false;             // fast reached the end, so there is no loop
};

What the interviewer is checking

The interviewer wants the constant-space two-pointer trick and, ideally, a clear argument for why the fast pointer must meet the slow one instead of skipping past it.

Mistakes to avoid

• Detecting loops by repeated values; different nodes can hold the same value.
• Calling fast.next.next without first checking that fast and fast.next are not null.
• Comparing slow and fast before moving them, so the shared starting node counts as a meeting.
• Forgetting the empty list and the one-node self-loop.

Follow-ups to expect

• How do you find the node where the loop starts? (Reset one pointer to head, step both by one.)
• How long is the loop? (After meeting, count steps until they meet again.)
• Can you find a duplicate in an array of 1..n the same way? (Treat values as next pointers.)

In real software

Cycle detection guards against infinite loops when following references: corrupted linked structures, redirect chains, symbolic links, and iterated functions in pseudo-random generators.

Practice next