Description

Floyd's cycle detection is used to do two things. Find if a cycle exists, and where the cycle started.
?

Reach for when

You have a graph or a linked list and want to find a cycle or start of it.

Runtime

O(n)

Visualization

Pseudocode

floyds(head):
	slow = fast = head
	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
		if fast is slow:
			A CYCLE EXISTS!
			pointer = head
			while pointer is not slow:
				pointer = pointer.next
				slow = slow.next
			FOUNT START OF CYCLE
			return pointer
	NO CYCLE

Code

def find_cycle_start(head):
	slow = fast = head
	while fast and fast.next:
		slow = slow.next            # +1
		fast = fast.next.next       # +2
		if fast is slow:            # they met → a cycle exists
			pointer = head
			while pointer is not slow:   # advance both by 1 until they meet
				pointer = pointer.next
				slow = slow.next
			return pointer          # start of the cycle
	return None                     # fast hit the end → no cycle