Check if a linked list is circular
Problem
Return true if the list is circular: following next pointers from the head eventually leads back to the head itself (not to some other node).
Example 1
Input: 1 → 2 → 3 → (back to 1) Output: true
Example 2
Input: 1 → 2 → 3 → null Output: false
Also asked as: Check if a linked list is a circular linked list
Test cases
Case 1
Input: [[1,2,3],0] Expected: true
Case 2
Input: [[1,2,3],-1] Expected: false
Case 3
Input: [[1],0] Expected: true
Case 4
Input: [[1],-1] Expected: false
Case 5
Input: [[1,2,3],1] Expected: false
View solutionHide solution1 approach
1. Find the cycle with fast/slow pointers, then check that head is on it
Time O(n)Space O(1)
A normal list ends in null, so the fast pointer falls off the end. If the pointers meet, there is a cycle, but it may start at a later node; walk once around the cycle to see whether it passes through head.
function isCircular(head) { if (!head) return true; let slow = head, fast = head; do { if (!fast || !fast.next) return false; // reached the end: no cycle slow = slow.next; fast = fast.next.next; } while (slow !== fast); // slow is somewhere on the cycle: circular only if head is on it too let n = slow; do { if (n === head) return true; n = n.next; } while (n !== slow); return false;}Simply walking until you return to head never stops on a list whose cycle starts at a later node.