Detect Loop in linked list

Easy

Problem

Return true if the linked list has a cycle, meaning some node's next pointer points back to an earlier node. Aim for O(1) extra space.

Example 1

Input:  3 → 2 → 0 → -4 → (back to 2)
Output: true

Example 2

Input:  1 → 2 → null
Output: false

Also asked as: detect and remove loop in a linked list · Write a program to Detect loop in a linked list

Test cases

Case 1

Input:    [[3,2,0,-4],1]
Expected: true

Case 2

Input:    [[1,2],0]
Expected: true

Case 3

Input:    [[1],-1]
Expected: false

Case 4

Input:    [[],-1]
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Floyd's tortoise and hare

Time O(n)Space O(1)

A fast pointer (2×) and slow pointer (1×) meet inside a cycle. O(1) space.

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

To find the loop start: after meeting, move one pointer to head and advance both 1× — they meet at the entry.

2. Hash set of visited nodes

Time O(n)Space O(n)

First node seen twice is on the loop. Simple, O(n) space.

function hasCycle(head) {
const seen = new Set();
for (let n = head; n; n = n.next) {
if (seen.has(n)) return true;
seen.add(n);
}
return false;
}