Circular Linked List

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.

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