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) { Node s = head Node f = 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