Detect a cycle (Floyd’s algorithm)

Easy TimeO(n) SpaceO(1)

Following a well-formed list eventually reaches the end. If some node points back to one already visited the walk never finishes, and the list has a cycle. Given the head of a list, return true when it contains one. The cycle need not include the head — it can start anywhere — an empty list has none, and the memory used must not grow with the length of the list.

Examples

Example 1

Input
head = buildCyclicList()
Output
true
The fourth node points back at the second, so the walk never reaches an end.

Example 2

Input
head = { val: 1, next: { val: 2, next: null } }
Output
false
Two nodes and then null: the walk finishes, so there is no cycle.

The Code

function buildCyclicList() {
  const a = { val: 1, next: null };
  const b = { val: 2, next: null };
  const c = { val: 3, next: null };
  const d = { val: 4, next: null };
  a.next = b;
  b.next = c;
  c.next = d;
  d.next = b;
  return a;
}
function hasCycle(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}
hasCycle(buildCyclicList());
Done
Step through hasCycle(buildCyclicList()) call by call

More like this

All linked lists examples (9) →