Skip to main content

11. Linked List Cycle

easyAsked at Riot Games

Detect whether a singly linked list contains a cycle — Floyd's tortoise-and-hare is the canonical low-memory check Riot uses for replication-graph loops.

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

Problem

Given the head of a linked list, determine whether the list has a cycle in it. Return true if any node is revisited by following the next pointers; otherwise return false.

Constraints

  • 0 <= nodes <= 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], pos=-1
Output
false

Approaches

1. Hash set of visited nodes

Walk the list and record every node reference; revisit means cycle.

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

Tradeoff:

2. Floyd's slow/fast pointers

Advance one pointer by 1 and another by 2; they meet inside any cycle. Riot servers reuse this exact cadence when sweeping for replication loops on hot paths.

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

Tradeoff:

Riot Games-specific tips

Riot expects O(1)-space reasoning for cycle detection — on a 30Hz server tick, the hash-set version's allocator pressure shows up immediately in their profiler traces.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →