Linked List Cycle — DSA

Problem

Given head, the head of a singly linked list, determine whether the list contains a cycle.

A cycle exists if some node can be reached again by repeatedly following next pointers: the last node's next points back to an earlier node, instead of to null. In that case, a naive traversal would loop forever.

3 → 2 → 0 → -4
    ↑        |
    └────────┘      (the tail links back to the node with value 2: cycle → true)

Return true if there's a cycle, and false otherwise.

The list may be empty, or have a single node (which may point to itself).
Follow-up: can you solve it using O(1) extra memory?

Examples

Example 1

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

Output: true

Explanation: Tail connects to node at index 1.

Example 2

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

Output: false

Explanation: No cycle.

Constraints

•The number of nodes is in the range [0, 10^4].

Hints

Hint 1

Floyd's cycle detection: fast pointer moves 2 steps, slow moves 1 — they meet if there's a cycle, since the fast pointer effectively 'laps' the slow one inside the loop.

Hint 2

A simpler brute force tracks every visited NODE in a hash set, checking for a repeat — correct in O(n) time, but uses O(n) space; Floyd's technique achieves the same result in O(1) space.

Solutions

public boolean hasCycleBruteForce(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    ListNode curr = head;
    while (curr != null) {
        if (!visited.add(curr)) return true; // add() returns false if curr was already present
        curr = curr.next;
    }
    return false;
}

Time: O(n) · Space: O(n)