LeetCode/141.Linked List Cycle

2개의 포인터를 둔다. 하나는 한 번에 한 칸씩 전진하고, 다른 하나는 한 번에 2칸씩 전진하는 녀석을. 다음과 같은 2가지로 나뉜다. 처음의 예외사항은 항상 체크를 해야 한다. nullptr이거나 1녀석이 혼자 사이클을 돌리고 있거나. 

1. Cycle이 있다면 2칸씩 전진하는 녀석이 1칸씩 전진하는 녀석을 따라잡는다
2. Cycle이 없다면 2칸씩 전진하는 녀석이 끝에 다다른다.

fast는 2칸씩 가니까 2칸 후가 nullptr인지만 보면 된다고 생각하기 쉬운데, 실제로는 fast->next==nullptr일 경우에 fast->next->next는 nullptr에 접근하려고 하려하기 때문에 2가지 모두 체크해봐야 한다.

class Solution {
public:
    bool hasCycle(ListNode *head) {
        
        if(head==nullptr)
            return false;
        if(head == head->next)
            return true;
        
        ListNode* slow = head;
        ListNode* fast = head->next;
        
        while(slow->next!=nullptr && fast->next!=nullptr && fast->next->next!=nullptr)
        {
            if(slow==fast)
            {
                return true;
            }
            
            slow = slow->next;
            fast = fast->next->next;
        }
        
        return false;
    }
};