DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Linked List Cycle

easyLinked list Must-do

Problem statement

You get the head of a singly linked list. Somewhere along the chain, a node's next pointer might point back to an earlier node, so following next would go round in a loop forever. Return true if the list contains such a loop, and false if following next eventually reaches the end (null).

You only receive head; you are not told where, or whether, the loop starts.

Examples

Example 1

Input: head = 5 -> 1 -> 8 -> 3, and the 3 node's next points back to the 1 node

Output: true

Explanation: Walking the list goes 5, 1, 8, 3, 1, 8, 3, ... and never ends.

Example 2

Input: head = 6 -> 9 -> null

Output: false

Explanation: The walk reaches null after two nodes.

Hints

Approach

Use Floyd's cycle detection (tortoise and hare).

  1. Start slow and fast at head.
  2. On each step, move slow by one node and fast by two.
  3. If fast or fast.next becomes null, the list has an end: return false.
  4. If slow and fast ever point to the same node, return true.

Why they must meet: once both are inside the loop, the gap between them shrinks by exactly one node per step, so it reaches zero within one lap and fast cannot jump over slow.

ComplexityTime O(n)Space O(1)
Python
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def hasCycle(self, head: ListNode | None) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
if slow is fast:
return True # fast lapped slow inside a loop
return False # fast hit the end

Follow-up questions

  • Return the node where the cycle begins (Linked List Cycle II).
  • Return the length of the cycle.

Frequently asked questions

fast moves two nodes, so both fast and fast.next must exist before you read fast.next.next. Checking only fast crashes on lists with an even number of nodes.

After slow and fast meet, move one pointer back to head and step both one node at a time. They meet again at the start of the loop. That is Linked List Cycle II.

Yes. Following a chain of redirects, symlinks, CNAME records or "depends on" pointers can loop, and tools guard against it either with a visited set or a hop limit.