Determine if a linked list is circular.

The idea here is to move a slow pointer and a fast pointer and if there is a circle, the pointers eventually meet at the same node.

At each step, slow pointer s moves one node and fast pointer f moves two nodes. If s enters a circle, f will be j nodes ahead of s. Since it’s a circle, it also means that f is k – j nodes behind s, where k is number of nodes in the circle. Because s moves forward one node at a time and f moves forward two nodes at a time, f gets one node closer to s at each step.

Since it takes at most k steps for f to meet with s at the same node, and k <= n where n is number of nodes, the runtime is O(n).

```bool isCircular(Node head) {

while (true) {
if (s.next)
s = s.next
else
return false

if (f.next && f.next.next)
f = f.next.next
else
return false

if (f == s)
return true
}
return false
}```

Here’s a bit of a math explanation for the circle.
k = number of nodes in circle
i = number of steps taken after s has entered circle
j = number of nodes f is ahead of s after s has entered circle
fp = position of fast pointer in circle
sp = position of slow pointer in circle

Here is the position sp and fp, at any step i
sp = i % k
fp = (2 * i + j) % k

And where sp = fp is where the two pointers meet, or
i % k = (2 * i + j) % k

Let’s do an example. For a circle of length k = 100 and a fast pointer j = 12 nodes ahead, find i where fp = sp.

When i is 0, the slow pointer is at 0 and the fast pointer is 12 nodes ahead just as we would expect.

0 % 100
(2 * 0 + 12) % 100

0 = sp
12 = fp

And when i = 88 steps taken, the two pointers meet. This can be simplified to k – j = 88.

88 % 100
(2 * 88 + 12) % 100

88 = sp
88 = fp

Scroll to top