Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/

풀이

문제가 좀 개판임
문제 설명이 개같음

말을 드럽게 어렵게 해놨음

그냥 딱 이거임

1. pos는 매개변수로 주어지지 않음
2. tail노드에서 next가 있을때 이때 next가 가리키는 노드를 pos라고 임의로 말함
3. 그러니까, 그냥 tail노드에서
   next가 nullptr이면 싸이클이 없는거고
   next가 특정 노드면 싸이클이 존재하는거임

1차 풀이

그냥 set을 써서 $O(n\log n)$으로 풀음

class Solution {
public:
    bool hasCycle(ListNode *head) {
        
        set<ListNode*> set;

        ListNode* n = head;

        bool isFound = false;

        while(n)
        {
            if(set.contains(n))
            {
                isFound = true;
                break;
            }

            set.insert(n);
            n = n->next;
        }

        return isFound;
    }
};

2차 풀이

문제에서 추가 도전사항을 제시해줌

지금은 set을 사용해서 $O(n)$의 메모리 공간을 사용함
이걸 $O(1)$, 즉, 추가 메모리 없이 해결해보라는거임

이건 투포인터를 써야함
핵심은 아래 내용임

1. 어짜피 tail->next는 싸이클이 있거나, nullptr임

그러니까 포인터 2개를 둬서
하나는 1칸씩 움직이고, 하나는 2개씩 움직여서
싸이클이 만들어지면 true,
2개씩 움직인 노드가 nullptr이면 false를 리턴하면 됨

왜 2개씩 움직이는거임? 3개는 안됨?

2개씩 움직여야하는 이유는
nullptr을 편하게 찾기 위해서임

nullptr->next는 에러터짐
근데 이걸 3개, 4개씩 하면 예외처리를 위해 if문이 오지게 쓰임

편하게 하려고 ㅇㅇ

class Solution {
public:
    bool hasCycle(ListNode *head) {

        if(!head) return false;
        
        ListNode* n = head;
        ListNode* nn = head->next;

        while(nn && nn->next)
        {
            if(n == nn) return true;

            n = n->next;
            nn = nn->next->next;

            if(!nn) return false;
        }

        return false;
    }
};

끝!