41.Linked List Cycle

EasyBlind 75Linked List · 7/11

Problem

Given head, the head of a linked list, determine whether the list contains a cycle — that is, whether some node can be reached again by repeatedly following next pointers.

Internally, a cycle is created by connecting the tail to the node at index pos (pos = -1 means no cycle), but pos is not passed to your function. Return true if there is a cycle, otherwise false.

Examples

Input:  head = [3, 2, 0, -4], pos = 1
Output: true
Explanation: The tail (-4) connects back to the node at index 1 (value 2).

Input:  head = [1, 2], pos = 0
Output: true
Explanation: The tail connects back to the head.

Input:  head = [1], pos = -1
Output: false
Explanation: Following next eventually reaches null.

Constraints

The number of nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked list.

💡 Key Insight

A list without a cycle always ends at null; a list with a cycle never does. To tell the two apart without extra memory, use two runners at different speeds (Floyd's tortoise and hare): if there is a loop, the fast runner laps the slow one and they must land on the same node; if not, the fast runner simply reaches null.

Brute Force (Look Back for Each Node)

TimeO(n²)SpaceO(1)

Intuition

In a cyclic list, there is exactly one node whose next points back to a node at the same or an earlier position. Walk the list keeping a position counter; for each node, scan the prefix of the list to see whether its next is one of the nodes already visited.

Algorithm

curr = head, pos = 0.
While curr != null:
- Walk probe from head through positions 0..pos; if probe == curr.next, return true.
- curr = curr.next, pos++.
Return false.

Visualization

3 -> 2 -> 0 -> -4 -> (back to 2)
pos 0 (3):  next=2, prefix [3]          no
pos 1 (2):  next=0, prefix [3,2]        no
pos 2 (0):  next=-4, prefix [3,2,0]     no
pos 3 (-4): next=2, prefix [3,2,0,-4]   2 found -> true

Code

java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode curr = head;
        int pos = 0;
        while (curr != null) {
            // Does curr.next point back to any node at position 0..pos?
            ListNode probe = head;
            for (int i = 0; i <= pos; i++) {
                if (probe == curr.next) {
                    return true;
                }
                probe = probe.next;
            }
            curr = curr.next;
            pos++;
        }
        return false;
    }
}

Complexity

Time: O(n²) — each node rescans the prefix before it.
Space: O(1) — just pointers and a counter.

Hash Set

TimeO(n)SpaceO(n)

Intuition

Remember every node you visit (by reference, not value). If you ever arrive at a node you have already seen, you have gone around a loop.

Algorithm

Create an empty HashSet<ListNode> seen.
For each node from head:
- If seen.add(node) returns false, return true.
Return false when null is reached.

Visualization

visit 3   seen={3}
visit 2   seen={3,2}
visit 0   seen={3,2,0}
visit -4  seen={3,2,0,-4}
visit 2   already in seen -> true

Code

java

import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<>();
        for (ListNode node = head; node != null; node = node.next) {
            if (!seen.add(node)) {
                return true; // visited this exact node before
            }
        }
        return false;
    }
}

Complexity

Time: O(n) — each node is visited at most once before detection.
Space: O(n) — the set may store every node.

Floyd's Tortoise and HareOptimal

TimeO(n)SpaceO(1)

Intuition

Move slow one step and fast two steps at a time. Without a cycle, fast hits null. With a cycle, once both are inside the loop the distance between them shrinks by exactly one node per step, so fast cannot jump over slow — they must meet.

Algorithm

slow = head, fast = head.
While fast != null && fast.next != null:
- slow = slow.next, fast = fast.next.next.
- If slow == fast, return true.
Return false.

Dry Run

flowchart LR
    N3["3"] --> N2["2"]
    N2 --> N0["0"]
    N0 --> N4["-4"]
    N4 -->|"cycle"| N2

step   slow   fast
start   3      3
1       2      0
2       0      2      (fast: 0 -> -4 -> 2)
3      -4     -4      slow == fast -> true

Code

java

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;       // 1 step
            fast = fast.next.next;  // 2 steps
            if (slow == fast) {
                return true;        // fast lapped slow inside a cycle
            }
        }
        return false; // fast reached the end: no cycle
    }
}

Complexity

Time: O(n) — before the cycle slow takes at most n steps, and inside the cycle fast closes the gap within one lap.
Space: O(1) — two pointers.

Complexity Comparison

Approach	Time	Space
Look Back for Each Node	O(n²)	O(1)
Hash Set	O(n)	O(n)
Floyd's Tortoise and Hare	O(n)	O(1)

Common Pitfalls

Checking slow == fast before moving them — they both start at head, so you would always return true.
Looping on fast.next != null without first checking fast != null, causing a NullPointerException.
Storing node values in the set instead of node references — duplicate values do not imply a cycle.
Forgetting the empty list: head == null must return false.