Linked List Cycle

PracticeNeetCode ↗LeetCode ↗

Given the head of a linked list, determine whether the list contains a cycle — some node's next eventually points back to a node earlier in the list.

Example

Key Pointers

• Floyd's tortoise-and-hare: a fast pointer moving 2 steps and a slow pointer moving 1 step will eventually meet if — and only if — a cycle exists.
• No extra memory needed, unlike tracking every visited node in a hash set.
• If fast (or fast.next) ever becomes None, the list terminates cleanly — there's no cycle.

Step-by-Step Analysis

1. Initialize slow = head, fast = head.
2. Loop while fast and fast.next are not None: move slow one step, fast two steps.
3. If at any point slow is fast, a cycle exists — return True.
4. If the loop ends because fast (or fast.next) is None, return False.

Complexity

Time: O(n) — Space: O(1)

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head: ListNode | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

Code Explanation

How the solution above works, piece by piece.

1. Two pointers start at the head: slow moves one step, fast two steps.
2. while fast and fast.next: if fast reaches the end, there is no cycle.
3. Once both are inside the cycle, the gap between them shrinks by one per step, so they can't jump past each other; they must meet.
4. slow is fast compares node identity, not values; different nodes can hold the same value.
5. O(n) time and O(1) space, versus O(n) space for a set of visited nodes.

Visual Walkthrough

Running it on [3, 2, 0, -4] with the tail linked to index 1:

Video Explanation

NeetCode — Linked Lists, LeetCode 141