Skip to main content
SeniorPath
Browse content
Menu / Close menu

March 24

Linked List Cycle

How to detect a cycle with fast and slow pointers and understand why different speeds eventually meet.

Linked List Intermediate 15 min TypeScript

#interviews#linked-list#two-pointers#cycle

Given a linked list, return true if it has a cycle and false otherwise.

In the original problem, you receive head. In the SeniorPath playground, the tests use:

  • values: the node values in order
  • pos: the index that the tail points back to

If pos = -1, the list ends in null.

Example:

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

That represents the last node pointing to the node at index 1.

What to notice before coding

  • Node values do not matter for cycle detection. The structure does.
  • If there is no cycle, traversal ends at `-1`.
  • If there is a cycle, a fast pointer eventually catches the slow one.

Common mistakes

  • forgetting that `pos = -1` means no cycle
  • moving the fast pointer without handling the case where it already reached the end

Step 1 - Ignore the format and focus on the structure

The real problem is still a linked list with a cycle.

Here the playground uses values and pos because an object with cyclic references does not fit well in JSON.

That changes the input shape, but not the core idea:

  • there is a "next"
  • that next either ends
  • or loops forever

Step 2 - Write the most direct baseline

The natural read is:

  • start from the first node
  • store which indexes you already visited
  • if you visit one again, there is a cycle

That works well.

The cost is extra memory.

Step 3 - Understand Floyd's intuition

If a cycle exists and:

  • one pointer moves slowly
  • the other moves quickly

at some point the fast one catches the slow one inside the loop.

If there is no cycle, the fast one reaches the end.

Step 4 - Think about "next" as a function

In this format, the next index is:

  • index + 1, while you are not at the last node
  • pos, when you are at the last node
  • -1, if there is no cycle

The algorithm stays the same.

The interactive editor needs JavaScript. You can still read the prompt and copy the starter code below.

Starter code

export function hasCycle(values: number[], pos: number): boolean {
  // `pos` is the index where the tail points back to, or -1 if there is no cycle
  // your solution here
  return false
}
solution.ts
Stuck? Hints available.

Haven't solved it yet?

Viewing the solution now may reduce learning. It's worth trying a bit more.

Open the reference solution

Without JavaScript, the reference solution is shown inline instead of in a dialog.

Solution

Final complexity

Time: O(n)

Space: O(1)

Solution 1 - Keep a Hash Set of visited nodes

Good baseline because it makes the meaning of “detect cycle” explicit.

function nextIndex(index: number, size: number, pos: number): number {
  if (index === -1 || size === 0) {
    return -1
  }

  if (index < size - 1) {
    return index + 1
  }

  return pos
}

export function hasCycle(values: number[], pos: number): boolean {
  const visited = new Set<number>()
  let current = values.length === 0 ? -1 : 0

  while (current !== -1) {
    if (visited.has(current)) {
      return true
    }

    visited.add(current)
    current = nextIndex(current, values.length, pos)
  }

  return false
}

It works, but it uses memory proportional to the path you walked.

Solution 2 - Floyd with fast and slow two pointers

Now you detect the cycle without storing visited nodes.

function nextIndex(index: number, size: number, pos: number): number {
  if (index === -1 || size === 0) {
    return -1
  }

  if (index < size - 1) {
    return index + 1
  }

  return pos
}

export function hasCycle(values: number[], pos: number): boolean {
  let slow = values.length === 0 ? -1 : 0
  let fast = values.length === 0 ? -1 : 0

  while (fast !== -1) {
    slow = nextIndex(slow, values.length, pos)
    fast = nextIndex(nextIndex(fast, values.length, pos), values.length, pos)

    if (slow !== -1 && slow === fast) {
      return true
    }
  }

  return false
}

The strong part here is the movement reasoning, not the input format.

What to say in the interview

A strong short explanation would be:

The baseline stores visited nodes in a Hash Set, but the better solution uses Floyd’s algorithm with two pointers. If a cycle exists, a fast pointer must eventually meet the slow one. If no cycle exists, the fast pointer reaches the end. That gives O(n) time with O(1) extra space.

That shows that you:

  • can justify fast and slow two pointers without a canned phrase
  • understand why the meeting happens
  • recognize when a Set can become a better algorithm

When this pattern shows up again

The same pattern comes back when you need to:

  • detect a cycle in a structure with a next relation
  • find a meeting point in circular traversal
  • recognize when different speeds reveal hidden structure

The point is not memorizing hasCycle.

The point is understanding why two pointers can prove that a loop exists.
Next challenge Invert Binary Tree Previous challenge Merge Intervals

Related challenges

Reverse Linked List

Merge Two Sorted Lists

Longest Substring Without Repeating Characters

Related articles

Thinking Before You Code in Interviews

Recognizing Problem Patterns

How to Explain Your Solution Without Getting Lost