Linked List Cycle

Problem in Plain English

You are given the head of a linked list where the tail may loop back to an earlier node. Return true when following next pointers revisits a node and false when the list ends.

Problem Statement

Given head, the head of a linked list, determine whether the list has a cycle. A cycle exists when some node can be reached again by continuously following the next pointer.

Return true when following next pointers revisits a node and false when the walk reaches null. Node values never decide the answer; only node identity does.

The notation pos describes the test fixture's tail connection; it is not an argument to the function. Leave all node values and next links unchanged. Assume a finite collection of nodes with stable next links during the call.

Constraints

The number of distinct reachable nodes is between $0$ and $10^4$ inclusive.
Node values lie between $-10^5$ and $10^5$ inclusive.
pos is minus one for no cycle, or a valid zero-based node index for the tail connection. It is fixture notation, not a function parameter.

Examples

Example 1

Input: head = [3,2,0,-4], pos = 1
Output: true

The four distinct nodes form A(3) → B(2) → C(0) → D(-4) → B(2). Revisiting node B proves a cycle; its value is not the criterion.

Example 2

Input: head = [1,2], pos = 0
Output: true

The second node links to the first, giving a two-node loop with no prefix before the entrance. Following next references never reaches null.

Example 3

Input: head = [1], pos = -1
Output: false

The only node has next = null. The walk ends after visiting it once, so the result is false.

Example 4

Input: head = [1,1], pos = -1
Output: false

The nodes have equal values but different identities, and the second points to null. Repeated data does not create a cycle.

Example 5

Input: head = [7], pos = 0
Output: true

The sole node points to itself. Both walkers return to that same object after their first movement.

Example 6

Input: head = [], pos = -1
Output: false

A null head has no reachable node and therefore no cycle.

Intuition

A linked list is a chain of node objects joined by next references. Revisiting the same object proves a cycle, even if its value is also stored elsewhere. In Example 1 label the four objects A, B, C and D: A → B → C → D → B. A set remembers these identities explicitly. Floyd's algorithm instead advances one reference by one hop and another by two; their meeting after movement proves the chain loops.

Approaches

Hash Set

Solution Details

Reveal Hash Set: intuition, complexity, and code

Intuition

Remember each node identity before following its next link. Encountering an identity already stored means the walk has returned to an earlier object, exactly the definition of a cycle. This easy baseline spends memory proportional to the reachable nodes but does not change their links.

Step-by-Step Logic

Create an empty set of identities and place the traversal pointer at head. Example 1 labels its objects A through D to distinguish identity from stored data.
While the pointer is non-null, check whether that exact object was recorded. If it was, return true before inserting or advancing.
Otherwise record its identity and move the pointer to its next object. The Example 1 table shows each pointer transition and the tail back-link.
If traversal reaches null, return false. The set retains identities only, and no node field is changed.

Why It Works

Before each membership test, the set contains exactly the identities already visited. A hit therefore proves the current object was reached earlier, so the intervening next links form a cycle. On a miss, recording the object and following its next link preserves the invariant. In an acyclic finite list all reachable objects are distinct and the walk reaches null, so false is correct. In a cyclic list the walk eventually revisits the entrance, so true is returned. Java uses an identity-backed set and Python stores id(node), avoiding value equality or custom equality overrides; JavaScript Set compares objects by reference.

Dry Run

Hash Set: variable states at each step
current before → after	identity already seen?	seen before	action / seen after
A(3) → B(2)	no	{}	record A; {A}
B(2) → C(0)	no	{A}	record B; {A,B}
C(0) → D(-4)	no	{A,B}	record C; {A,B,C}
D(-4) → B(2)	no	{A,B,C}	record D; {A,B,C,D}
B(2) → return	yes	{A,B,C,D}	return true; no advance

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(n)

Let n be the number of distinct reachable nodes. Each is inserted once, followed by at most one repeated membership test, giving O(n) expected time under expected constant-time hashing. The set or identity map allocates O(n) entries and table capacity; Python stores O(n) identity integers. No nodes are created or copied, and input links and values remain unchanged.

Code

Solution.java

1import java.util.Collections;2import java.util.IdentityHashMap;3import java.util.Set;4
5// Omit this definition when the platform supplies ListNode.6class ListNode {7    int val;8    ListNode next;9    ListNode(int val) { this.val = val; }10}11
12class Solution {13    public boolean hasCycle(ListNode head) {14        Set<ListNode> visited = Collections.newSetFromMap(new IdentityHashMap<ListNode, Boolean>());15        while (head != null) {16            if (!visited.add(head)) return true;17            head = head.next;18        }19        return false;20    }21}

Hints

Hint 1

Remembering visited nodes works because a cycle is exactly a node reached twice, which suggests a set first.

Hint 2

To drop the set, send two walkers at speeds one and two: an ending list drops the fast walker off at null.

Hint 3

Guard the fast walker with checks on both fast and fast.next before each double step.

Edge Cases

A null head returns false without dereferencing any pointer.
One node with a null next link returns false; one node pointing to itself returns true after the first movement.
A cycle may start at head or after a long noncyclic prefix; both produce a meeting.
Distinct nodes with repeated values are not a cycle. Test an acyclic chain whose every value is equal.
Both odd and even acyclic lengths must exit safely when the fast reference or its next link reaches null.

Common Mistakes and Interview Tips

Comparing val fields instead of object identity reports a cycle for different nodes holding equal values.
Comparing the initially equal pointers before moving reports true for every nonempty list.
Dereferencing fast.next.next without checking fast and fast.next crashes on short or acyclic lists.
In Python, value-based equality or an unhashable custom node can break a node-object set; this code stores id(node) and uses is for the race.
Changing next links or stamping visited values mutates the input and may corrupt later traversals.
Trying to traverse a cyclic list to null while building its length never terminates. No length or pos input is needed.

Key Takeaway

When a path may loop, race a slow and a fast walker: a meeting proves a cycle and an off-the-end fall proves there is none.