Skip to main content

20. Linked List Cycle

easyAsked at Datadog

Detect whether a linked list contains a cycle. Datadog uses this as the Floyd-tortoise warmup before more complex cycle-detection problems in their dependency-graph traversals.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Datadog phone screen — graded on Floyd's tortoise and hare.
  • Blind (2025-10)— Recurring at Datadog onsites.

Problem

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. Return true if there is a cycle in the linked list. Otherwise, return false.

Constraints

  • The number of the nodes in the list is in the range [0, 10^4].
  • -10^5 <= Node.val <= 10^5

Examples

Example 1

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

Example 2

Input
head = [1,2], pos = 0
Output
true

Example 3

Input
head = [1], pos = -1
Output
false

Approaches

1. Hashset of visited nodes

Walk forward; if you revisit a node, there's a cycle.

Time
O(n)
Space
O(n)
function hasCycle(head) {
  const seen = new Set();
  while (head) {
    if (seen.has(head)) return true;
    seen.add(head);
    head = head.next;
  }
  return false;
}

Tradeoff: O(n) space. Correct, but Datadog explicitly asks for O(1) memory in their dependency-graph context.

2. Floyd's tortoise and hare (optimal)

Two pointers, slow advances 1 step, fast advances 2. If there's a cycle, they meet. If fast hits null, no cycle.

Time
O(n)
Space
O(1)
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;
}

Tradeoff: Constant space. Datadog-canonical: works on streaming graph traversals where O(n) memory would blow the budget.

Datadog-specific tips

Datadog interviewers will ask 'why does it work?' — the answer is that if there's a cycle of length L, the gap between slow and fast closes by 1 each step inside the cycle, so they meet within L steps. Bonus: discuss LC 142 (find the cycle's start) — same algorithm with a clever second-phase trick.

Common mistakes

  • Checking slow === fast BEFORE advancing — they start equal, so you'd return true immediately on any list.
  • Forgetting the fast.next null check — crashes on an odd-length acyclic list.
  • Comparing slow.val === fast.val — could falsely return true on a list with duplicate values.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

  • Linked List Cycle II (LC 142) — find where the cycle starts.
  • Happy Number (LC 202) — same cycle detection on an implicit graph.
  • Datadog-style: detect a cycle in a metric-dependency graph in O(1) memory.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is it called tortoise and hare?

The slow pointer (tortoise) moves 1 step at a time; the fast pointer (hare) moves 2. In a cycle, the hare laps the tortoise.

Does it work if the list is too short for fast to take 2 steps?

The while condition (fast && fast.next) guards against null deref. If either is null, the list is acyclic.

Practice these live with InterviewChamp.AI

Drill Linked List Cycle and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →