Here is solutions for Linked List Cycle Detection

1. Understand the Problem

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

• A cycle exists if some node’s next pointer points back to a previous node in the list.

2. Clarify Constraints & Ask Questions

1. Can the input be empty (head = None)?

=> Yes, return False (no cycle).

1. What is the expected output?

=> Boolean (True if a cycle exists, otherwise False).

1. Can the linked list contain only one node?

=> Yes. If the node points to itself (next = head), it’s a cycle.

1. Are there any restrictions on modifying the list?

=> Usually, we should avoid modifying the list.

1. What is the expected time and space complexity?

=> Ideally Time: O(n) and Space: O(1).

3. Explore Examples

4. Brainstorm 2 - 3 Solutions

4.1. Solution 1: Use a Hash Set (Naive)

• Traverse list, store visited nodes.

• If we encounter a visited node → cycle detected.

• Time: O(N).

• Space: O(N).

4.2. Solution 2: Floyd’s Cycle Detection (Optimized) – “Tortoise and Hare”

Use two pointers:

- slow moves 1 step at a time

- fast moves 2 steps at a time

• If they ever meet → cycle exists

• If fast or fast.next = None → no cycle

  • Time: O(N).

  • Space: O(N).

Idea: A fast and a slow start in the same start, and it will meet each other definately.

5. Implement solutions

5.1. Hash Set

Idea: Because 1 node can have only 1 next => So a node point to null, or point to another node.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        seen = set()
        cur = head
        while cur:
            if cur in seen:
                return True
            seen.add(cur)
            cur = cur.next
        return False

• Time: O(N).

• Space: O(N).

5.2. Fast And Slow Pointers

Idea: The fast and slow pointer start with the same point will always meet each others.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

• Time: O(N).

• Space: O(1).

6. Dry run examples

1 → 2 → 3 → 4 → 5
            ↑   ↓
            ← ← ←