Interview challenge · easy · linked-list, two-pointers, floyd
Linked List Cycle
El reto
El enunciado va en inglés, igual que en el vídeo.
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 -> falseIdea: 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).
La solución
# Linked List Cycle - ayotl.dev
class Node:
def __init__(self, val):
self.val, self.next = val, None
def has_cycle(head):
# tortoise: 1 step, hare: 2 steps
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True # hare lapped it
return False # hare hit the end
a, b, c, d = map(Node, (3, 2, 0, -4))
a.next, b.next, c.next = b, c, d
d.next = b # -4 points back to 2
print(has_cycle(a))
d.next = None
print(has_cycle(a))
$ python3 linked_list_cycle.py
True
False