Skip to main content

141. Linked List Cycle

easyAsked at Cisco

Linked List Cycle at Cisco is the second-most common pointer warm-up after Reverse Linked List. The interviewer wants Floyd's tortoise-and-hare so you can detect the loop in O(1) extra space. The hash-set version is the fallback when you can't articulate why two pointers eventually meet.

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

Source citations

Public interview reports confirming this problem appears in Cisco loops.

  • Glassdoor (2026-Q1)— Cisco SDE-I phone screens report Linked List Cycle as a recurring warm-up.
  • Levels.fyi (2025-12)— Cisco new-grad interview reports list this as a standard 10-minute round.

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
  • pos is -1 or a valid index in the linked-list.

Examples

Example 1

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

Explanation: Tail node connects back to node at index 1.

Example 2

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

Example 3

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

Approaches

1. Hash set of visited nodes (brute force)

Walk the list and record every node reference. If you ever revisit, there's a cycle. If you hit null, there isn't.

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

Tradeoff: Simple to reason about. Wrong space complexity for the rubric — Cisco wants O(1). Bring this up as the strawman before pivoting to Floyd's.

2. Floyd's tortoise and hare (optimal)

Two pointers: slow moves one step, fast moves two. If there's a cycle they meet inside it. 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: O(1) extra space, single pass. The 'why does this work?' explanation: once both pointers are inside the cycle, fast gains one step per iteration on slow. In a cycle of length C, they meet in at most C iterations. That's the full intuition.

Cisco-specific tips

Cisco interviewers expect Floyd's by name. Say 'I'll use Floyd's tortoise-and-hare with two pointers' before writing code, then explain why fast catches slow inside the cycle. If you only know the hash-set version, write it but immediately follow with 'O(1) variant is Floyd's — slow + fast pointer, they meet inside a cycle.'

Common mistakes

  • Forgetting to check `fast.next` before `fast.next.next` — null dereference when the list ends.
  • Initializing fast to `head.next` instead of `head` — works but creates a subtle off-by-one in the LC 142 follow-up.
  • Returning false too early — must wait for the loop to exit (fast hits null) before concluding no cycle.

Follow-up questions

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

  • Linked List Cycle II (LC 142) — return the NODE where the cycle starts. Floyd's again: after they meet, reset slow to head and step both one at a time.
  • Happy Number (LC 202) — Floyd's on a sequence of digit-squared-sums (same algorithm, different graph).
  • Find the Duplicate Number (LC 287) — Floyd's on an array treated as a linked list.

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 Floyd's actually work?

Once both pointers enter the cycle of length C, fast gains 1 net step per iteration on slow. So after at most C iterations, fast = slow (mod C). The pre-cycle 'tail' doesn't matter because both pointers enter at the same time once slow walks the tail.

Is the hash-set version acceptable?

It correctly returns true/false, so yes on rubric. But Cisco interviewers specifically expect O(1) on this question because the canonical answer is Floyd's. Use the hash-set only if you can't recall the two-pointer trick — and follow up immediately with 'I know there's an O(1) variant called Floyd's.'

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →