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

#leetcode #python #algorithms #datastructures

Easy — Linked List | Two Pointers | Hash Table

The Problem

Given the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if there is some node in the list that can be reached again by continuously following the next pointer.

Approach

Uses Floyd's Cycle Detection Algorithm (tortoise and hare) with two pointers moving at different speeds. If there's a cycle, the fast pointer will eventually meet the slow pointer; if there's no cycle, the fast pointer will reach the end.

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

Code

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