Detect a loop in LL

New·#141·Easy·Linked List

Use Floyd's Tortoise and Hare algorithm to detect cycles in O(n) time and O(1) space

Asked at:AmazonMicrosoftGoogleGoldman Sachs

Practice mode

Step

Initialization

slow and fast pointers set to head.

Cache workspace

Floyd's Cycle Finding

Step 1 / 8init

100%

list

slow & fast

→

cycle start

→

→null

slow val =

fast val =

has cycle =

yes

Explanation

Initialize slow and fast pointers at the head of the list (1). The tail points back to index 2 (value 3).

step 1 / 8

Space play← → stepHome reset

TimeO(n)·SpaceO(1)

Floyd's Cycle Finding

1class Solution {
2    hasCycle(head) {
3        let slow = head;
4        let fast = head;
5 
6        while (fast !== null && fast.next !== null) {
7            slow = slow.next;
8            fast = fast.next.next;
9 
10            if (slow === fast) {
11                return true; // Loop detected
12            }//slow: 1fast: 1
13        }
14 
15        return false;
16    }
17}

slow1

fast1

Command Palette

Detect a loop in LL

Detect a loop in LL