LinkedList가 순환(cycle)을 가지고 있는지 어떻게 확인할까? 🐇💨 🐢

LinkedList에 순환이 있는지 확인하는 가장 대표적인 알고리즘으로 플로이드의 사이클 검출 알고리즘(Floyd's Cycle Detection Algorithm) 이 있다.

 

이 알고리즘은 흔히 토끼와 거북이 알고리즘으로 불린다.

 

토끼와 거북이 알고리즘

1. 빠른(hare) 포인터와 느린(tortoise)포인터, 두 개의 포인터를 사용한다.

2. 빠른 포인터는 한 번에 두 개의 노드를 건너뛰고 느린 포인터는 한 번에 한 개의 노드를 건너뛰는 방식으로 움직인다.

3. 연결리스트에 사이클이 없다면, 빠른 포인터는 먼저 끝(null)에 도착하게 된다.

4. 만약 사이클이 있다면, 빠른 포인터와 느린 포인터는 언젠가 만나게 된다.

 

구현

public Boolean hasCycle() {
    Node<E> slow = this.head;
    Node<E> fast = this.head;

    while (fast != null && fast.next != null) {
        slow = slow.next; // 한 칸씩 점프
        fast = fast.next.next; // 두 칸씩 점프

        if (slow == fast) {
            return true; // 언젠가 만난다면 사이클 있는 것
        }
    }

    return false;
}