[알고리즘] Floyd's Tortoise and Hare Algorithm (LeetCode #141)

Floyd's Tortoise and Hare Algorithm

Floyd's cycle-finding algorithm은 다른 속도를 가진 두 개의 포인터를 사용하는 포인터 알고리즘이다. 

 

Tortoise and Hare 알고리즘을 통해 순환 여부를 알 수 있다. 

 

 

1. 포인터 2개를 선언한다. (slow, fast)

2. slow 포인터는 한 번에 한 칸씩 이동한다

3. fast 포인터는 한 번에 두 칸씩 이동한다. 

4. 만약 두 포인터가 어느 순간에 만나게 된다면, cycle이 존재한다. 

 

 

 

더 쉽게 이해를 해보려면, 트랙을 달리고 있는 두 사람을 생각해보면 된다. 

 

트랙은 cycle이 존재하는 원형 모양이다. 

A는 빠른 속도로, B는 느린 속도로 달리고 있다. 

두 사람이 같은 지점에서 달리기를 시작했을 때, A는 B보다 한 바퀴를 더 돈 후 두 사람은 같은 지점에서 만나게 된다. 

 

 

LeetCode #141

Given head, the head of a linked list, determine if the linked list has a cycle in it.

 

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

 

Return true if there is a cycle in the linked list. Otherwise, return false.

주어진 linked list의 head를 이용하여, 해당 linked list에 cycle이 존재하는지를 찾는 문제이다. 

 

 

플로이드의 순환 알고리즘을 알기 전 짠 코드이다. 

class Solution(object):
    def hasCycle(self, head):
        cnt = 0
        p = head
        while p != None:
            q = head
            flag = -1
            while q != p.next:
                flag += 1
                q = q.next
            if flag < cnt:
                return True 
            p = p.next
            cnt += 1
        return False

포인터 p가 node를 하나씩 이동해 나가면서 cnt의 값을 하나씩 증가시키고,

q는 head에서 부터 p에 이르기 까지 flag의 값을 하나씩 증가시킨다. 

 

만약, p의 값이 None이라면 순환하지 않기 때문에 False를 return하고

flag < cnt 인 경우 (p는 q보다 한 바퀴 더 돌아서 둘이 마주친 상태), cycle이 존재하므로 True를 반환한다. 

 

 

 

위의 문제를 Tortoise and Hare Algorithm을 이용해 해결하면,

class Solution(object):
    def hasCycle(self, head):
        fast = head
        slow = head
        while fast != None and fast.next != None:
            fast = fast.next.next
            slow = slow.next
            if fast is slow:
                return True
        return False

fast와 fast의 다음 노드가 존재하는 동안 (fast는 2칸 씩 이동하기 때문에, fast 다음 노드도 null 값이 아닌지 확인해야한다. ), fast는 2칸 씩 이동하고, slow는 한 칸씩 이동한다. 

 

fast와 slow가 만나면 cycle이 존재하고, 

만약 fast 또는 fast의 다음 노드가 존재하지 않는다면, cycle이 존재하지 않는다. 

 

 

<참고>

https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_Tortoise_and_Hare

Cycle detection - Wikipedia

https://www.youtube.com/watch?v=RRSItF-Ts4Q&t=10s