Easy

Linked List Cycle

An easy Linked List problem included in Apna College, Love Babbar 450, Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.

Topic: Linked List
Sheets: 3
Core for: 3 roles
Platform: LeetCode

Practice in the compiler Watch this solved step by step

The problem

Given the head of a linked list, determine whether the list contains a cycle.

Example 1

Input: [3,2,0,-4] with tail connecting to index 1
Output: true

Example 2

Input: [1,2] with no cycle
Output: false

Example 3

Input: [1] with no cycle
Output: false

Constraints

0 <= n <= 10^4
-10^5 <= Node.val <= 10^5

How to think about it

Updated 2026-09-09

A cycle has no end, so a single pointer running indefinitely cannot tell if it is making forward progress or retracing steps. Two runners on a circular track moving at different speeds must eventually occupy the exact same spot, reducing infinite path detection to pointer coincidence.

Approaches, worst first

Visited node set
time O(n) · space O(n)
Traverse the list and insert each node memory reference into a hash set. If curr is ever found in the set, a cycle exists; if null is reached, the list terminates. Guarantees detection but incurs linear auxiliary storage.
Fast and slow pointersWrite this one
time O(n) · space O(1)
Advance slow by one hop and fast by two hops. If fast or fast.next hits null, the list is linear and terminates. If fast catches slow at the identical node reference, a cycle is confirmed. Each iteration reduces the loop distance between runners by one.

Where people lose marks · 3

Checking fast.next.next inside the loop guard without first ensuring fast and fast.next are non-null causes null pointer exceptions on odd-length lists.
Comparing node values instead of object memory addresses produces false cycle detections whenever duplicate numeric values appear across distinct nodes.
Initializing slow and fast both to head and testing equality inside a while condition causes an immediate zero-step premature exit before any hops occur.

Full solution

Floyd's fast/slow pointers: O(n) time, O(1) space, and the runners meet at the same node reference iff a cycle exists.

Python

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


def has_cycle(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

JavaScript

class ListNode {
  constructor(val = 0, next = null) {
    this.val = val;
    this.next = next;
  }
}

function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Try it in the editor

The theory behind it

Linked List — the ground this problem stands on. All Linked List problems

What Linked List is

A linked list is a chain of separate cargo cars connected by coupling hooks, scattered anywhere across memory rather than sitting in a tidy contiguous row. Each car, called a node, holds a single piece of data and a pointer directing traffic to the address of the next car in line. Because nodes connect only by directional links, jumping straight to the tenth car is impossible without walking past the first nine.

When to reach for it

Choose a linked list when a problem requires frequent insertions and deletions at known positions without shifting whole blocks of surrounding memory. Problems mentioning pointer splicing, reversing subsequences in place, merging sorted streams, or detecting cycles in linear chains strongly point here. It is ideal when total capacity is unpredictable and memory allocation must happen one individual node at a time.

How the pattern works

Think in terms of pointer rewiring before dereferencing. Keep a dummy head node pointing to the start of the list so modifications to the initial item do not require separate edge logic. Always save references to neighboring nodes into temporary variables before cutting or redirecting forward links. When diagnosing loops or locating middle nodes, advance two references simultaneously at differing velocities so traversal completes without supplementary storage.

What each operation costs

Operation	Time
insert or delete at the head	O(1)
insert or delete after a known node	O(1)
find an element by value or position	O(n)

What usually goes wrong with Linked List

Losing access to the remainder of the chain by overwriting a next reference before caching the downstream node address in a temporary variable.
Attempting to read properties of a null node reference after walking one step beyond the tail or advancing a fast runner without checking its next step.
Creating an accidental infinite cycle by pointing a trailing node back into earlier segments of the chain without severing old outgoing links.

Which roles need this problem

Linked List is a core topic for these 3 roles — if you're targeting one of them, this problem is early in your path, not optional.

SDE / Backend Engineer Embedded / Firmware Engineer Storage Engineer

Secondary for 5 more roles, including Full-Stack Developer, Android Developer, iOS Developer.

Track this in your role's order

Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.

Start free