Interview challenge · easy · linked-list, two-pointers, floyd

Linked List Cycle

The challenge

Given head, the head of a linked list, determine whether the list has a cycle: a node that can be reached again by continuously following next.

Example

3 -> 2 -> 0 -> -4
     ^          |
     +----------+       ->  true

1 -> 2 -> None          ->  false

Idea: Floyd's tortoise and hare. A slow pointer moves one step, a fast one two steps. If there is a cycle the fast pointer laps the slow one and they meet; if not, the fast one falls off the end. Time O(n), space O(1).

The solution

1# Linked List Cycle - ayotl.dev
2class Node:
3    def __init__(self, val):
4        self.val, self.next = val, None
5
6
7def has_cycle(head):
8    # tortoise: 1 step, hare: 2 steps
9    slow = fast = head
10    while fast and fast.next:
11        slow = slow.next
12        fast = fast.next.next
13        if slow is fast:
14            return True  # hare lapped it
15    return False  # hare hit the end
16
17
18a, b, c, d = map(Node, (3, 2, 0, -4))
19a.next, b.next, c.next = b, c, d
20d.next = b  # -4 points back to 2
21print(has_cycle(a))
22d.next = None
23print(has_cycle(a))

$ python3 linked_list_cycle.py

True

False

The video

Watch on YouTube →