EasyLinked ListTwo PointersHash Table

Linked List Cycle

1 approach, code in all languages

Given the head of a singly linked list, decide whether the list contains a cycle and return true if it does, otherwise false.

A cycle exists when some node can be reached again by repeatedly following next pointers. Internally this is described by a position that the tail links back into, but that index is not given to your function; you must detect the loop purely by traversing the nodes.

Example 1

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

Output: true

The last node points back to the node at index 1 (value 2), so following next repeats forever.

Example 2

Input: head = [1], pos = -1

Output: false

A single node whose next is null has no cycle.

Constraints

The number of nodes is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 (no cycle) or a valid 0-based index into the list.

Floyd's Tortoise and Hare

Run two pointers at different speeds; a meeting proves a cycle exists.

Loading animation…

Intuition

Imagine two runners on a track, one moving one step per turn and one moving two. On a straight path with no loop the fast runner simply reaches the finish and stops. But if the path curves back into a loop, the fast runner keeps circling and eventually laps the slow runner, so at some point they occupy the same node. Detecting that collision tells us a cycle is present. If instead the fast pointer ever reaches the end of the list, there is no loop. This uses constant memory, unlike hashing every visited node.

Algorithm walkthrough

1Start both slow and fast pointers at the head.
2While fast and fast.next are non-null, advance slow by one node and fast by two nodes.
3After each move, compare the pointers; if slow equals fast they have collided inside a loop, so return true.
4If the loop terminates because fast fell off the end, the list is linear.
5Return false once fast reaches null.

Implementation

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True
        return False

Time

O(n)

Space

O(1)

The pointers meet within a linear number of steps; no hash set required.

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in

Back to Linked List

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI