Floyd's Cycle Detection 알고리즘

플로이드의 순환 찾기 알고리즘은 포인터 두 개를 이용해 트리 내에 존재하는 사이클을 빠르게 찾을 수 있는 알고리즘이다. 

 

 

 

개념

1. slow와 fast라는 이름을 가진 포인터 두 개를 사용해 각각 한 칸, 두 칸씩 이동시킨다.

 

2. 둘 중 어느 것도 null값에 도달하기 전까지 반복해서 이동시키면서 두 포인터가 만나는 지점이 있는지 매번 확인한다.

 

 

이때 만약 사이클이 없다면, 각자 다른 간격으로 이동하는 두 포인터는 만나지 않고 리스트의 끝에 도달한다.

 

그러나 만약 사이클이 있다면, 리스트의 끝에 도달할 수 없기 때문에 반복해서 돌다가 특정 지점에서 만나게 된다.

 

 

 

 

구현 코드

//관련 문제: https://leetcode.com/problems/linked-list-cycle/

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *slow = head;
        ListNode *fast = head;
        
        while(slow && fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            
            if(slow == fast)
                return true;
        }
        return false;
    }
};