Leetcode - 141. Linked List Cycle

문제

배열이 주어지고 각 링크드리스트 노드를 나타낸다. pos는 마지막 노드의 next 포인터 위치를 나타낸다. -1 이면 next 포인터는 NULL이다. 이 링크드리스트가 사이클을 갖는지 아닌지 판단하라.

Input: head = [3,2,0,-4], pos = 1
Output: true

해결 O(n) / O(n)

굉장히 흥미로운 문제였다. 노드를 순회하면서 노드의 포인터값을 해시테이블의 key로해서 빈도를 저장했다.
답은 맞았는데, 솔직히 이렇게 해도 되는건지 모르겠다... 포인터주소의 hash collision처리도 안되어있고.. 다음에 다른 방법으로 한번 더 풀어봐야할듯!

1. Constraints
 - single node can be cycle?
 - how many node? 0 ~ 10000
 - the valses can be duplicated? 
 - if pos == -1, what is tail->next? NULL?
2. Ideas
3. TestCases

#define HSIZE 200001
bool hasCycle(struct ListNode *head) {
    struct ListNode *node = head;
    struct ListNode *table[HSIZE] = {0};
    memset(table, 0, sizeof(struct ListNode *) * HSIZE);
    
    for (;node != NULL; node = node->next) {
        if (table[(int)node % HSIZE])
            return true;
        table[(int)node % HSIZE]++;
    }
    return false;
}

해결 O(n) / O(1)

추가 메모리를 사용하지 않고 공간복잡도를 O(1)푸는 방법.
서로 속도가 다른 two pointer기법이다. 한칸씩 이동하는 slow와 두칸씩 이동하는 fast포인터로 루프를 돌리다보면 사이클이 있을때, 이 둘은 언젠가는 만난다. 아주 신박한 방법! (참고로 풀이가 링크드 리스트의 중간노드 찾는것과 동일하다. 루프 종료후 slow가 중간노드)

bool hasCycle(struct ListNode *head) {
    if (head == NULL)
        return false;
    struct ListNode *slow = head, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast)
            return true;
        slow = slow->next;
        fast = fast->next->next;
    }
    return false;
}