Check if a linked list is circular

Easy

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

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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.