linked list 안에 cycle이 있는지 확인하는 방법.(토끼와 거북이 알고리즘)

https://leetcode.com/problems/linked-list-cycle/ 문제로 설명함.

설명 : https://leetcode.com/problems/linked-list-cycle/discuss/44539/AC-Python-76ms-Floyd-loop-detection-in-7-lines

코드는 위에꺼 그대로 가져옴.

def hasCycle(self, head):
    slow = fast = head
    while fast and fast.next:
        # fast는 두칸 뒤로 가고, slow는 한칸만 뒤로 감.
        # cycle이 없으면 while fast and fast.next에서 False가 나와서 루프가 끝날 것이고,
        # cycle이 있으면 fast가 속도가 더 빠르므로 slow를 결국에는 따라잡아서 루프가 있다는것을 확인 가능함.
        # 그냥 fast만 앞으로 한칸씩가고 slow는 가만히 있으면 안되나? 했었는데
        # 루프의 끝이 꼭 처음과 연결된다는 보장이 없고, 중간에도 생길 수 있으므로 slow도 계속 이동해줘야함.
        fast = fast.next.next
        slow = slow.next
        if slow == fast:
            return True
    return False

# 16 / 16 test cases passed.
# Status: Accepted
# Runtime: 76 ms
# 96.56%

토끼와 거북이 알고리즘이라고 함.

https://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

https://heod.tistory.com/2

바로 위 블로그에 순환이 시작되는 첫번째 위치를 찾는 방법도 나와있다.