LeetCode 141: Linked List Cycle — Step-by-Step Visual Trace

Source: Dev.to

Problem Description

Given the head of a linked list, determine if the linked list contains a cycle. A cycle exists if some node can be reached again by continuously following the next pointer.

Approach

Use Floyd’s Cycle Detection Algorithm (also known as the “tortoise and hare” technique). Two pointers traverse the list at different speeds:

• Slow pointer moves one step at a time.
• Fast pointer moves two steps at a time.

If a cycle is present, the fast pointer will eventually meet the slow pointer. If there is no cycle, the fast pointer will reach the end of the list (None).

Complexity Analysis

• Time: (O(n)) – each node is visited at most a constant number of times.
• Space: (O(1)) – only two pointers are used regardless of list size.

Reference Implementation (Python)

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head or not head.next:
            return False

        slow = head
        fast = head.next

        while slow != fast:
            if not fast or not fast.next:
                return False
            slow = slow.next
            fast = fast.next.next

        return True

Interactive Visualization

Open interactive visualization – step through each line with TraceLit, the visual algorithm tracer for LeetCode practice.