DSAPrep
EasyLinked List

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail's next pointer is connected to. 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
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints

  • The number of the 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.
Follow-up: Can you solve it using O(1) (i.e. constant) memory?
View original on LeetCode ↗

The obvious way to detect a cycle is to remember every node visited and check if you ever revisit one. The constant-space trick is to use two pointers moving at different speeds — if there is a loop, the faster one is guaranteed to lap the slower one from behind.

Hash Set of Visited Nodes

Time O(n)Space O(n)

Walk the list, storing each node’s identity in a set. If you ever encounter a node already in the set, the next pointers have looped back on themselves.

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


class Solution:
    def hasCycle(self, head: ListNode | None) -> bool:
        seen = set()
        node = head
        while node:
            if node in seen:
                return True
            seen.add(node)
            node = node.next
        return False

Correct and simple, but storing a reference to every visited node costs O(n) extra space — for a problem that is really just “did we ever come back to somewhere we have been,” that is more memory than necessary.

Floyd's Cycle Detection (Slow / Fast Pointers)

OptimalTime O(n)Space O(1)

Move a slow pointer one step at a time and a fast pointer two steps at a time. If there is no cycle, fast reaches the end first and the loop terminates. If there is a cycle, fast enters it first and, moving twice as fast as slow, closes the gap between them by exactly one node per iteration — so it is guaranteed to eventually land on the same node as slow.

class Solution:
    def hasCycle(self, 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

Tracing head = [3,2,0,-4] with the tail’s next wired back to node 2 (index 1) — a cycle:

3
2
0
-4
▲slow
▲fast
1 / 4

Start: slow and fast both at node 3. Note the tail (-4) loops back to node 2.

Why it’s correct: if a cycle exists, once fast enters it, the distance between fast and slow (measured along the cycle) shrinks by exactly one node every iteration, since fast gains one extra step per round — so it cannot skip over slow and must eventually meet it exactly. Complexity: fast traverses at most ~2n node visits before either exiting or meeting slow → O(n) time, and only two pointer variables are used → O(1) space — optimal, matching the follow-up requirement.