Detect Loop in linked list
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
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;}