Linked List Cycle

Difficulty: Easy Source: NeetCode

Problem

Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle if some node in the list 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 (0-indexed). Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list, otherwise return false.

Example 1: Input: head = [3,2,0,-4], pos = 1 Output: true

Example 2: Input: head = [1,2], pos = 0 Output: false

Constraints:

• The number of nodes in the list is in the range [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked list

Prerequisites

Before attempting this problem, you should be comfortable with:

• Linked List Traversal — following .next pointers through a list
• Hash Sets — O(1) lookup for tracking visited elements
• Two-Pointer Technique — using slow and fast pointers moving at different speeds

1. Brute Force / Naive Approach

Intuition

Keep a hash set of every node we’ve visited. As we walk the list, if we ever encounter a node we’ve already seen, there must be a cycle. If we reach None, the list is finite and has no cycle. The catch: we’re storing node references (not values, since values can repeat) in the set.

Algorithm

1. Initialize an empty set visited.
2. Walk the list with pointer cur.
3. If cur is already in visited, return True.
4. Add cur to visited and advance to cur.next.
5. If the loop ends (we hit None), return False.

Solution

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

def build_list_with_cycle(values, pos):
    """Build a linked list with an optional cycle.
    pos = -1 means no cycle; otherwise tail.next points to node at index pos."""
    if not values:
        return None
    nodes = [ListNode(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos != -1:
        nodes[-1].next = nodes[pos]  # create cycle
    return nodes[0]

def hasCycle_brute(head):
    visited = set()
    cur = head
    while cur:
        if cur in visited:
            return True
        visited.add(cur)
        cur = cur.next
    return False

# Test cases
head1 = build_list_with_cycle([3, 2, 0, -4], pos=1)
print(hasCycle_brute(head1))  # True

head2 = build_list_with_cycle([1, 2], pos=0)
print(hasCycle_brute(head2))  # True

head3 = build_list_with_cycle([1], pos=-1)
print(hasCycle_brute(head3))  # False

head4 = build_list_with_cycle([3, 2, 0, -4], pos=-1)
print(hasCycle_brute(head4))  # False

Complexity

• Time: O(n) — visit each node at most once
• Space: O(n) — storing all visited nodes in the set

2. Floyd’s Cycle Detection (Optimal)

Intuition

This is the classic “tortoise and hare” algorithm. Use two pointers: slow moves one step at a time, fast moves two steps at a time. If there’s no cycle, fast will hit None and we’re done. If there is a cycle, both pointers end up going around the loop — and since fast is lapping slow, they will eventually meet at the same node.

Think of it like a circular running track: if two runners start at the same point and one runs twice as fast, the faster runner will eventually lap the slower one and they’ll be at the same position again.

No cycle:
slow: 1 -> 2 -> 3 -> None  (fast gets to None first, exit)

With cycle [3,2,0,-4], cycle at index 1:
Step 0: slow=3, fast=3
Step 1: slow=2, fast=0
Step 2: slow=0, fast=2
Step 3: slow=-4, fast=-4  <-- they meet! cycle confirmed

Algorithm

1. Initialize slow = head and fast = head.
2. While fast and fast.next are not None:
   • Move slow one step: slow = slow.next.
   • Move fast two steps: fast = fast.next.next.
   • If slow == fast, return True.
3. Return False (fast reached the end, no cycle).

Solution

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

def build_list_with_cycle(values, pos):
    if not values:
        return None
    nodes = [ListNode(v) for v in values]
    for i in range(len(nodes) - 1):
        nodes[i].next = nodes[i + 1]
    if pos != -1:
        nodes[-1].next = nodes[pos]
    return nodes[0]

def hasCycle(head):
    slow = head
    fast = head

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

    return False

# Test cases
head1 = build_list_with_cycle([3, 2, 0, -4], pos=1)
print(hasCycle(head1))  # True

head2 = build_list_with_cycle([1, 2], pos=0)
print(hasCycle(head2))  # True

head3 = build_list_with_cycle([1], pos=-1)
print(hasCycle(head3))  # False

head4 = build_list_with_cycle([3, 2, 0, -4], pos=-1)
print(hasCycle(head4))  # False

head5 = build_list_with_cycle([], pos=-1)
print(hasCycle(head5))  # False

Complexity

• Time: O(n) — both pointers traverse at most O(n) steps before meeting or exiting
• Space: O(1) — only two pointer variables, no extra data structures

Common Pitfalls

Checking slow == fast before moving them. Both start at head, so they’re equal initially — don’t check before moving or you’ll always return True. The check should be inside the loop after advancing.

Checking fast.next in the while condition. You need fast and fast.next because you’re jumping two steps: fast.next.next. If you only check fast, you’ll get an AttributeError when fast is the last node and you try to access fast.next.next.

Storing node values instead of node references in the brute force. Values can repeat! [1, 1, 1] with no cycle would incorrectly return True. Always add the node object itself to the set, not its .val.