Skip to main content

141. Linked List Cycle

easyAsked at Elastic

Detect whether a linked list contains a cycle. Elastic uses Floyd's tortoise-and-hare algorithm here as a proxy for distributed-systems intuition — detecting liveness vs. livelock in a cluster follows the same principle of needing two probes at different rates to distinguish 'still making progress' from 'spinning in a loop'.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

  • Glassdoor (2025-11)— Elastic SWE candidates report cycle detection appearing as a pointer-reasoning test in early technical rounds.
  • Blind (2025-08)— Elastic interview threads mention Floyd's algorithm as a question that opens into distributed-systems liveness discussions.

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 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 (pos is used internally to create the cycle).

Examples

Example 1

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

Explanation: The tail node connects back to node at index 1, forming a cycle.

Example 2

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

Explanation: The tail connects back to the head.

Example 3

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

Explanation: No cycle; the single node points to null.

Approaches

1. Hash set

Store each visited node reference in a Set. If you encounter a node already in the set, a cycle exists.

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

Tradeoff: Simple and correct. O(n) space. Good starting point to establish correctness before optimizing.

2. Floyd's tortoise and hare (two pointers)

Use two pointers: slow moves one step, fast moves two steps. If there is a cycle, fast will eventually lap slow and they will meet. If there is no cycle, fast reaches null.

Time
O(n)
Space
O(1)
function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

Tradeoff: O(n) time, O(1) space — optimal. The canonical solution. Always prefer this over the hash set when asked to minimize space.

Elastic-specific tips

Elastic interviewers appreciate when you explain WHY fast laps slow: inside a cycle of length c, fast gains 1 step per iteration on slow, so they meet within c steps of fast entering the cycle — O(n) total. Then prepare for the follow-up: find the cycle start node (LC 142). The entry point is found by resetting one pointer to head after detection and advancing both at speed 1 until they meet.

Common mistakes

  • Checking fast === null without also checking fast.next === null — fast.next.next throws if fast.next is null.
  • Comparing node values instead of node references — two nodes can have the same value without being the same node.
  • Advancing fast before checking for meeting — check slow === fast after each advance step.
  • Not handling head === null or single-node inputs — the while condition covers these.

Follow-up questions

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

  • Linked List Cycle II (LC 142) — find the exact node where the cycle begins.
  • Happy Number (LC 202) — uses the same two-pointer cycle detection on a sequence of digit-square sums.
  • How does cycle detection relate to deadlock detection in distributed systems?

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 does fast always lap slow if a cycle exists?

Once both pointers are inside the cycle of length c, fast is gaining exactly 1 step per iteration relative to slow. After at most c iterations, the gap closes to 0 modulo c, so they meet.

Why check fast !== null AND fast.next !== null?

fast.next.next requires fast.next to be non-null first. Checking both conditions prevents a null-pointer exception when the list has an even or odd number of nodes.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →