Linked List Cycle I

Problem Link

141. Linked List Cycle – LeetCode

Problem Statement

Given the head of a singly linked list, determine if the linked list has a cycle in it.

A linked list has a cycle if a node can be reached again by continuously following the next pointer.

Return true if there is a cycle in the linked list. Otherwise, return false.

Examples

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list where the tail connects to the second node.

Example 2:

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

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: No cycle.

Constraints

• The number of nodes in the list is in the range [0, 10⁴]

• -10⁵ <= Node.val <= 10⁵

• pos is the index of the node where the tail connects. -1 if there is no cycle.

Intuition

If there’s a cycle, two pointers moving at different speeds will eventually meet inside the loop.

This is called Floyd’s Cycle Detection Algorithm (Tortoise and Hare).

Approach: Two Pointers (Floyd’s Algorithm)

1. Initialize two pointers: slow and fast, both at the head.

2. Move slow by one step, and fast by two steps.

3. If fast ever equals slow, a cycle exists.

4. If fast or fast.next becomes null, the list ends → no cycle.

Java Code

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) return true;
        }

        return false;
    }
}

Time and Space Complexity

Dry Run

Input:

[3 → 2 → 0 → -4]
          ↑     ↓
           ← ← ←

• slow = 3, fast = 3

• After a few steps: slow and fast meet at node 2

• Cycle detected → return true

Alternate Approaches

Using HashSet:

public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) return true;
        visited.add(head);
        head = head.next;
    }
    return false;
}

• Time: O(n)

• Space: O(n)

Conclusion

This problem is a classic use of the fast and slow pointer technique for cycle detection. The O(1) space solution is optimal and often applied in advanced linked list problems involving loops or revisits.