Linked List Cycle

EasyLinked List · Fast & Slow Pointers🧩 Fast & Slow Pointers LeetCode #141 ↗Updated Oct 30, 2026

Problem

You get the head of a singly linked list. Some node's next pointer may lead back to an earlier node, so following links would go round forever. Return true if such a loop exists, otherwise false. (The test harness describes the loop with pos, the index the tail connects to, or -1 for none — you never receive it.)

Inputhead = [3,2,0,-4], pos = 1Outputtrue (tail -4 links back to 2)

Inputhead = [1,2], pos = 0Outputtrue

Inputhead = [1], pos = -1Outputfalse

0 ≤ n ≤ 10⁴ · -10⁵ ≤ Node.val ≤ 10⁵ · Follow-up: use O(1) extra memory.

Try it yourself

Java

class Solution {
    public boolean hasCycle(ListNode head) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Two runners on a circular track: if one moves twice as fast, it must eventually catch up with the slower one from behind. On a straight (acyclic) list the fast runner simply falls off the end.

PatternFast & Slow Pointers

Instinct A next-step function you can follow (list nodes, digit-square sums, array-as-pointers) and you need a cycle, its entry, or the middle in O(1) space.

Memory hack Tortoise and hare - on a loop track the hare laps the tortoise; restart the tortoise at the gate and they meet at the loop's door.

Open the Fast & Slow Pointers guide →

Approaches

Brute ForceRemember Visited Nodes (HashSet)

Time O(n)Space O(n)

Walk the list and store each node reference (not its value — values can repeat). If we ever reach a node already in the set, the walk has looped. Reaching null means the list ends, so there is no cycle.

Java

public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    for (ListNode cur = head; cur != null; cur = cur.next) {
        if (!visited.add(cur)) return true; // seen this exact node before
    }
    return false;
}

Linear and simple, but stores up to n references — fails the follow-up.

OptimalFloyd’s Tortoise & Hare

Time O(n)Space O(1)

slow advances one node, fast two. Without a cycle, fast hits null first. With one, once both are inside the loop the gap between them shrinks by exactly 1 per step, so they meet within one lap — at most O(n) steps in total.

Java

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true; // hare caught the tortoise
    }
    return false;
}

Dry run[3,2,0,-4], pos = 1

s slowf fast changed

start
3
s f
2

0

-4

both at head
step 1
3

2
s
0
f
-4

s=2, f=0
step 2
3

2
f
0
s
-4

f: -4 → 2 (loop)
step 3
3

2

0

-4
s f
meet ⇒ true ✔

Constant memory, single pass — the classic answer.

Pro tip

Extend it: after they meet, restart one pointer at head and step both by one — they meet again at the cycle's entry (LC 142).

At a glance

Level	Approach	Time	Space
Brute Force	Remember Visited Nodes (HashSet)	`O(n)`	`O(n)`
Optimal	Floyd’s Tortoise & Hare	`O(n)`	`O(1)`

Common pitfalls

Checking only fast != null — fast.next.next then throws NPE.
Comparing node values instead of references — duplicate values give false positives.
Testing slow == fast before moving — they start equal, so it always says true.

Interview tips

Mention the HashSet idea in one line, then go straight to Floyd for O(1) space.
Explain why they must meet: the gap closes by one each step inside the loop.
Check aloud: empty list, single node without loop, single node pointing to itself.

Pattern

Fast & slow pointers → detect loops, find middles or cycle entries in linked structures without extra memory.

My notes saved in this browser