Linked List Cycle

L6 Medium Linked List

Concept

Floyd's technique sends two runners around the list at different speeds; in a cycle, the fast one loops back onto the slow one.

Some linked lists never end: following next pointers eventually revisits an earlier node in a loop. Given its head, return true if a cycle exists and false if the list terminates.

Examples

▸ head = [3, 2, 0, -4], pos = 1

→ true

▸ head = [1, 2], pos = 0

→ true

▸ head = [1], pos = -1

→ false

Progressive Hints

Hint 1 · Nudge

A tortoise and a hare: if the hare ever laps the tortoise, there's a loop.

Hint 2 · Plan

Move a slow pointer one step and a fast pointer two steps each round. If the fast pointer reaches nil, the list ends normally. If slow and fast ever meet, there's a cycle.

Hint 3 · Approach

slow = head, fast = head. While fast and fast.next exist: slow = slow.next; fast = fast.next.next; if slow == fast return true. Return false.

Output

// Run your code to see the output here.