Linked List Cycle

problem

링크드 리스트가 주어졌을 때, 순환하는 구조인지 판별하는 문제입니다.
https://leetcode.com/problems/linked-list-cycle

solution

class Solution {
public:
    bool hasCycle(ListNode *head) {
        map<ListNode*,int> m; 
        while(head != NULL){
            if(m.find(head) == m.end()){
                m[head] = head->val;
            }else{
                return true;
            }
            head = head->next;
        }
        return false;
        
    }
};

처음에 짠 코드입니다. map 자료구조를 이용해서 넣고 한칸씩 전진하면서 찾아서 발견하면 순환하는 것이므로 true를 리턴합니다.

코드의 문제점은 가장 안좋은 경우에는 원이 마지막 노트에서 마지막으로 두번째에 순환구조가 연결되어 있다면,
map에 n-1개의 노드가 들어가고, find()의 iter이 돌아가는 횟수가
1,2,3,4,5,6,7,8.....n-2까지 가므로 O(n^2)이 될것입니다.

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

와... 어떻게 이런 생각을 할 수 있을까, 추가적인 메모리 소모도 없고
코드도 간결하다. 빠르게 다가가는 iter가 순환형 구조에서는 언젠가 따라잡으니까 (간격이 한칸 씩 줄어든다.) 대단하다는 생각이 들었다.