[Algorithm] 토끼와 거북이 알고리즘, 플로이드의 순환 탐지 알고리즘

연결리스트에서 순환 즉 사이클이 있는지 확인 하는 알고리즘

 

다짜고짜 코드 

func hasCycle(head *ListNode) bool {
    if head == nil || head.Next == nil {
        return false
    }

    slow := head
    fast := head

    for fast != nil && fast.Next != nil {
        slow = slow.Next       // 한 번에 한 칸 이동
        fast = fast.Next.Next  // 한 번에 두 칸 이동

        if slow == fast {      // 두 포인터가 만나면 사이클이 존재
            return true
        }
    }

    return false
}

 

원리는 fast 는 두칸씩 slow 는 한칸씩 움직여서 결국에는 둘이 만난다는 원리 이다. 혹시나 tail 이 nil 을 가리키고 있어서

둘 중 하나가 nil 을 마주하면 사이클이 없는 거고 빠른애랑 느린애랑 둘이 만나면 사이클이 있는 거다.

 

빡대가리라서 왜 반더시 만나는지 좀 와닿지가 않았다. 하지만 아무리 교차 검증해도 사이클이 있다면 둘은 만난다. 한놈이 빠르기 때문에.. 뭔가 두칸씩 펄쩍펄쩍 뛰니까 딱딱딱 홀수번째에 만나서 안만나지는 거 아냐!? 라고 생각해도 결국 짝수번째에 만난다.

아무리 생각해도 직관적으로 와 닿지 않는데 그렇다고 받아들여야겠다. 양자역학처럼 나의 멍청한 뇌가 거부하는 알고리즘이다.