SimuVedaAlgorithms Lab Open in the lab

Lists, stacks & queues / Intermediate

Floyd's Cycle Detection Visualizer

slow moves 1 step, fast moves 2. With a cycle, fast laps slow and they meet. Without one, fast reaches null.

Start the Floyd's Cycle Detection simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(1)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. The last node links back to index 1, so there is a cycle. Both pointers start at the head.
  2. slow moves 1 step to 2. fast moves 2 steps to 0.
  3. slow moves 1 step to 0. fast moves 2 steps to 5.
  4. slow moves 1 step to -4. fast moves 2 steps to 2.
  5. slow moves 1 step to 5. fast moves 2 steps to -4.
  6. slow moves 1 step to 7. fast moves 2 steps to 7.
  7. slow and fast meet at 7. There is a cycle.

Try it with your own input →

Floyd's cycle detection in Java, Python, C++, C and JavaScript

boolean hasCycle(ListNode head) {
  ListNode slow = head, fast = head;
  while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
  }
  return false;
}
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False
bool hasCycle(ListNode* head) {
  ListNode *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return true;
  }
  return false;
}
int hasCycle(struct ListNode* head) {
  struct ListNode *slow = head, *fast = head;
  while (fast && fast->next) {
    slow = slow->next;
    fast = fast->next->next;
    if (slow == fast) return 1;
  }
  return 0;
}
function hasCycle(head) {
  let slow = head, fast = head;
  while (fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }
  return false;
}

In an interview

LeetCode 141, Linked List Cycle (and 142 to find where the cycle starts).

A HashSet of visited nodes also works, but uses O(n) memory. The follow-up is always "can you do it in O(1) space?"

More lists, stacks & queues