Detect Cycle in Linked List

Problem Statement

Given the head of a linked list, determine if the list has a cycle in it. A cycle exists if a node’s next pointer points back to a previous node.

Example: Input: 3 → 2 → 0 → -4 (with -4.next = node at index 1), Output: true

Approach 1: Hash Set

Explanation: Store visited nodes in a set. If a node repeats, cycle exists.

Time Complexity: O(n)

Space Complexity: O(n)

visited = set()
while head != NULL:
    if head in visited:
        return true
    visited.add(head)
    head = head.next
return false

Approach 2: Floyd’s Cycle Detection

Explanation: Use two pointers (slow and fast). If they meet, cycle exists.

Time Complexity: O(n)

Space Complexity: O(1)

slow = head
fast = head
while fast != NULL and fast.next != NULL:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return true
return false