(Easy - Fast & Slow Pointers) Leetcode - 141. Linked List Cycle

이 문제는 Linked-List가 주어졌을 때 리스트에 Cycle이 존재하는지 찾는 문제입니다.

Cycle이란 이전에 방문했던 곳을 연결된 노드를 타고 갔을 때 다시 방문하게 되어서 결국 계속해서 도는 구간을 의미합니다.

 

노드의 값에 음수도 존재하기에 unordered_map을 활용해 이전에 노드를 방문한 적이 있는지 확인해 재방문하는 것이라면

Cycle로 판단하는 구조로 문제를 풀었습니다.

 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
     bool hasCycle(ListNode *head) {
        std::unordered_map<ListNode*, int> visited;

        while (head) {
            if (visited[head]) // 재방문 확인
                return true;
            visited[head] = 1; // 방문했다는 의미
            head = head->next;
        }
        return false;
    }

 

노드를 거쳐갔는지 계속 확인하는 방법도 있지만 포인터를 두 개 사용해 문제를 풀 수 있습니다.

Linked-List에서 런너 기법, Fast and Slow Pointers라는 방법이 있습니다.

평범한 Linked-List에서 사용하면 fast가 2번씩 가는 동안 slow가 한 번씩 이동해 각각 fast는 list의 맨 끝, slow는 중간에 오게 됩니다.

하지만 Cycle이 있는 Linked-List에서 이 방법을 사용하면 Cycle에 의해 두 포인터가 무한하게 계속 Cycle 구간을 돌게됩니다.

이때 fast와 slow의 이동 속도가 다른데 무한하게 돌다보면 결국 한 노드에서 만나게 되어있습니다.

만약 만났다면 slow를 list의 맨 처음으로 이동한 뒤 fast와 slow 포인터들을 같은 속도로 한 칸씩 이동시키다 다시 만나는 구간이 Cycle의 시작노드가 됩니다.

이 알고리듬을 Floyd's Cycle-Finding 알고리듬이라고 부릅니다.

 

이 문제에서는 Cycle이 있는지만 판별하면 되므로 두 포인터가 만나면 true를 반환해주면 됩니다.

 

    // Floyd's Cycle-Finding 알고리듬
    bool hasCycle(ListNode* head) {
        if (!head) return false;
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) // 두 포인터가 만나면 Cycle이 있는 것
                return true;
        }

        return false;
    }