Linked List Cycle

Problem Description

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

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

Intuition

Imagine two runners on a circular track. If one runner is faster than the other, the faster runner will eventually lap the slower one - they will meet at some point. This is the core idea behind Floyd's Cycle Detection Algorithm, also known as the Tortoise and Hare Algorithm.

We use two pointers:

Slow pointer (tortoise): moves one step at a time
Fast pointer (hare): moves two steps at a time

If there's a cycle, the fast pointer will eventually catch up to the slow pointer inside the cycle. If there's no cycle, the fast pointer will reach the end of the list (null).

Visual Walkthrough

Consider a linked list with a cycle: 3 → 2 → 0 → -4 → (back to 2)

Step 1: Start both pointers at head

3

→

2

→

0

→

-4

→

2

slow and fast both at 3

Step 2: slow moves 1, fast moves 2

3

→

2

→

0

→

-4

→

2

slow at 2, fast at 0

Step 3: Continue moving

3

→

2

→

0

→

-4

→

2

slow at 0, fast at -4 (which points back to 2)

Step 4: They meet!

3

→

2

→

0

→

-4

→

2

Both slow and fast at 2 - Cycle detected!

Solution

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

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        # Handle edge case: empty list or single node
        if not head or not head.next:
            return False

        # Initialize slow and fast pointers
        slow = head
        fast = head

        # Move pointers until they meet or fast reaches end
        while fast and fast.next:
            slow = slow.next          # Move slow by 1
            fast = fast.next.next     # Move fast by 2

            if slow == fast:         # Cycle detected!
                return True

        # Fast reached end - no cycle
        return False

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        // Handle edge case: empty list or single node
        if (head == null || head.next == null) {
            return false;
        }

        // Initialize slow and fast pointers
        ListNode slow = head;
        ListNode fast = head;

        // Move pointers until they meet or fast reaches end
        while (fast != null && fast.next != null) {
            slow = slow.next;           // Move slow by 1
            fast = fast.next.next;      // Move fast by 2

            if (slow == fast) {           // Cycle detected!
                return true;
            }
        }

        // Fast reached end - no cycle
        return false;
    }
}

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    bool hasCycle(ListNode *head) {
        // Handle edge case: empty list or single node
        if (head == nullptr || head->next == nullptr) {
            return false;
        }

        // Initialize slow and fast pointers
        ListNode* slow = head;
        ListNode* fast = head;

        // Move pointers until they meet or fast reaches end
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;           // Move slow by 1
            fast = fast->next->next;     // Move fast by 2

            if (slow == fast) {             // Cycle detected!
                return true;
            }
        }

        // Fast reached end - no cycle
        return false;
    }
};

Key Insight

Why does this work?

If there's a cycle, think of it as a circular track. The fast pointer gains 1 position on the slow pointer every step (fast moves 2, slow moves 1, so relative speed = 1).

If the cycle has k nodes, the fast pointer will catch the slow pointer in at most k steps. It's like running on a track - the faster runner will always lap the slower one eventually.

Complexity Analysis

Time Complexity: O(n)

In the worst case, we traverse each node once. If there's a cycle, the fast pointer catches up in at most n steps. If no cycle, fast pointer reaches the end in n/2 iterations.

Space Complexity: O(1)

We only use two pointers (slow and fast) regardless of the input size. This is the optimal space solution for this problem.

Alternative Approach: Hash Set

We could also use a hash set to track visited nodes. As we traverse, if we encounter a node already in the set, there's a cycle.

seen = set()
while head:
    if head in seen:
        return True
    seen.add(head)
    head = head.next
return False

Pros: Simpler to understand

Cons: O(n) space complexity

AlgoExplained.dev