Linked List Cycle Solutions & Complexity

1. Define the problem

Linked List Cycle

Given values representing the nodes of a singly linked list and pos, the index the tail connects back to (or -1 for no cycle), determine whether the list has a cycle in it. A cycle exists if some node can be reached again by continuously following the next pointer. Use fast and slow pointers : the fast pointer moves two steps for every one step of the slow pointer. If the two pointers ever meet, the list has a cycle; if the fast pointer reaches the end, it does not.

Constraints

The number of nodes in the list is in the range [0, 10⁴].
-10⁵ ≤ values_i ≤ 10⁵
pos is -1 or a valid index in the linked list.

Example

Inputvalues = [3, 2, 0, -4], pos = 1

Outputtrue

Explanation The tail node (-4) connects back to the node at index 1 (value 2), forming a cycle that the fast and slow pointers eventually detect.

2. Know the words first

In plain terms

Linked list: A chain of nodes where each node just points to the next one, unlike an array where all the values sit together in one contiguous block.
Cycle: When a node's next pointer loops back to point at an earlier node instead of the chain ending, so following it forever never reaches an end.

3. Visualize the solution

Fast and slow pointers detect a cycle by meeting

3-4

Statusinit

slow and fast both start at index 0 (value 3).

What happens in this step

slow = 0 (value 3), fast = 0 (value 3)

Both pointers start together at the head before the loop runs.

Step 1 of 4

Steps to visualize

Point both slow and fast at the head of the list.
Advance slow one step and fast two steps on each iteration.
If fast reaches the end of the list, there is no cycle.
If slow and fast ever land on the same node, a cycle exists.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Fast and slow pointers detect a cycle by meeting

3-4

Statusinit

slow and fast both start at index 0 (value 3).

What happens in this step

slow = 0 (value 3), fast = 0 (value 3)

Both pointers start together at the head before the loop runs.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

function hasCycle(values, pos) {
  if (values.length === 0) {
    return false;
  }

  const nodes = values.map((val) => ({ val, next: null }));
  for (let i = 0; i < nodes.length - 1; i++) {
    nodes[i].next = nodes[i + 1];
  }
  if (pos >= 0) {
    nodes[nodes.length - 1].next = nodes[pos];
  }

  let slow = nodes[0];
  let fast = nodes[0];

  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) {
      return true;
    }
  }

  return false;
}

Time: O(n)
Space: O(1) (excluding the constructed list)

6. Test cases

Test cases

Input	Expected	Covers
`values = [3, 2, 0, -4], pos = 1`	`true`	example from the docstring
`values = [3, 2, 0, -4], pos = -1`	`false`	same list with no cycle
`values = [1], pos = -1`	`false`	a single node with no cycle
`values = [1], pos = 0`	`true`	a single node that cycles back to itself
`values = [1, 2], pos = 0`	`true`	the tail connects back to the head
`values = [1, 2], pos = -1`	`false`	a short list with no cycle

Linked List Cycle