Linked List Cycle

How it works

We use two pointers moving through the list at different speeds:

• slow moves one step at a time
• fast moves two steps at a time

If the list has a cycle, the fast pointer will eventually "lap" the slow pointer, meaning they will meet at some node inside the cycle.

If the list has no cycle, the fast pointer will reach the end (null) and the loop stops.

This method is efficient and uses constant extra space.

Steps

1. Initialize two pointers:
   • slow = head
   • fast = head
2. Move through the list:
   • slow moves one step.
   • fast moves two steps.
3. If at any point slow == fast, a cycle exists, return true.
4. If fast reaches the end (null or fast.next is null), no cycle exists, return false.

Complexity

• Time complexity: O(n)
• Space complexity: O(1)

Things to watch for

Not Checking if Fast Pointer Can Advance Safely

Before moving the fast pointer two steps, you must verify both fast and fast.next are not null. Checking only fast != null before accessing fast.next.next causes a null pointer exception when the list has an odd number of nodes without a cycle.

Comparing Node Values Instead of Node References

The cycle detection requires comparing whether two pointers reference the same node object, not whether they have the same value. Using value equality (slow.val == fast.val) incorrectly detects cycles when two different nodes happen to have the same value.

from typing import Optional

# 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

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

class Solution {
public:
    bool hasCycle(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;

        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;

            if (fast == slow) {
                return true;
            }
        }

        return false;
    }
};