Linked List Cycle

Try It Yourself

Use the editor below to determine whether following next pointers can loop forever. Move one pointer one step and another pointer two steps.

Submit your implementation when it passes the examples. Handle empty lists, ordinary endings, and a node that points to itself.

Linked List Cycle

easyLinked List · Fast and Slow Pointers25 minLC 141

Problem

Given the head of a singly linked list, return true when following next pointers eventually visits a node again.

Return false when traversal reaches null. Do not modify the list.

Example 1:

Input: head = [3, 2, 0, -4], tail connects to index 1

Output: true

Example 2:

Input: head = [1, 2], tail connects to no node

Output: false

Constraints

0 ≤ number of nodes ≤ 10,000
The list contains at most one cycle.

0 attempts

Solution

The slow pointer advances one node while the fast pointer advances two. Inside a cycle, the faster pointer eventually catches the slower pointer.

If fast or fast.next becomes null first, the list has an ordinary end and therefore no cycle.

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;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	The pointers meet or reach the end after a linear number of movements.
Auxiliary space	`O(1)`	Only the slow and fast node references are stored.