(algorithm) 링크드리스트에 사이클 있는지 추가 메모리 없이 검사하는 법

연결 리스트가 어딘가에서 자기 자신으로 돌아오는 사이클이 있는지 판별해야 하는데, 방문한 노드를 set에 다 담아서 확인하는 방식 말고 메모리를 거의 안 쓰는 방법이 있다고 들었어요.

두 포인터 쓰는 거라고 해서 이렇게 짜봤습니다.

slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False

느린 포인터는 한 칸, 빠른 포인터는 두 칸씩 가다가 둘이 같은 노드면 사이클이 있다고 판단하는 건데요. 궁금한 게, 사이클이 있으면 둘이 반드시 만난다는 보장이 진짜 있는 건가요? 한 칸 차이로 계속 엇갈려서 영원히 안 만날 수도 있을 것 같은데 왜 꼭 만나는지 직관이 안 잡힙니다.

그리고 사이클이 없을 때는 fast가 끝(None)에 닿아서 끝난다는 것까지는 알겠어요. 시간이 O(n), 공간이 O(1)인 것도 맞는지 확인 부탁드려요.