[알고리즘] Leetcode. Linked List Cycle 4개의 해결 방법

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

linked list에 cycle이 존재하는지 묻는 문제

Solution

1. Hashing

목록을 하나씩 탐색하고 노드 주소를 해시 테이블에 계속 넣습니다. 어느 시점에서든 null에 도달하면 false를 반환하고 현재 노드의 다음이 Hash에 이전에 저장된 노드 중 하나를 가리키면 true를 반환합니다.

(null에 도달한다는 것은 loop가 없는 linear linked list 라는 말)

 

시간 복잡도: O(n)

공간 복잡도: O(n)

var hasCycle = function(head) {
        var s = new Set();
        while (head != null) {
            // hashmap을 탐색했을 때 같은 node가 들어있다는 건 cycle이 존재한다는 말.
            if (s.has(head))
                return true;
 
            // 처음에는 node를 하나씩 넣어주고 두 번째 탐색시에 같은 노드가 있는지 알아본다
            s.add(head);
 
            head = head.next;
        }
 
        return false;
};

 

2. Mark Visited Nodes (연결 리스트 데이터 구조를 수정함)

- 첫 번째 솔루션과 같은 방법. 다른 점은 hash table을 사용하는 대신 연결 리스트 데이터 구조를 수정한다.

연결목록을 탐색하고 방문한 곳을 마킹한다. 마킹한 곳을 다시 방문한다면 loop가 있다는 걸 알게 된다. 

 

각 노드에 방문 플래그가 있습니다.
연결 목록을 탐색하고 방문한 노드를 계속 표시합니다.
방문한 노드가 다시 보이면 루프가 있는 것입니다. 이 솔루션은 O(n)에서 작동하지만 각 노드에 대한 추가 정보가 필요합니다.
기본 데이터 구조를 수정할 필요가 없는 이 솔루션의 변형은 해시를 사용하여 구현할 수 있습니다. 방문한 노드의 주소를 해시에 저장하기만 하면 해시에 이미 존재하는 주소가 표시되면 루프가 있습니다.

 

시간 복잡도: O(n)

공간 복잡도: O(1)

var hasCycle = function(head) {
    while (head != null) {
        // If this node is already traverse
        // it means there is a cycle
        // (Because you we encountering the
        // node for the second time).
        // flag에 1이 있다는 건 두 번째 탐색이라는 의미이므로 cycle이 존재한다.
        if (head.flag == 1)
            return true;
  
        // If we are seeing the node for
        // the first time, mark its flag as 1
        // 첫 번째 탐색에는 flag에 1을 넣어준다
        head.flag = 1;
  
        head = h.next;
    }
    return false;
};

 

3. Floyd's Cycle-Finding Algorithm

- 유명하고 가장 빠른 방법

두 개의 포인터를 사용하여 연결 리스트를 탐색합니다.
한 포인터(slow_p)를 1만큼 이동하고 다른 포인터(fast_p)를 2만큼 이동합니다.
이러한 포인터가 동일한 노드에서 만나면 루프가 있습니다. 포인터가 만나지 않으면 연결 목록에 루프가 없습니다.

 

시간 복잡도: O(n)

공간 복잡도: O(1)

var hasCycle = function(head) {
    if (!head) return false;

    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    
    return false;
};

 

 

4. Mark Visited Nodes (연결 리스트 데이터 구조를 수정하지 않음)

이 방법에서는 임시 노드가 생성됩니다. 순회하는 각 노드의 다음 포인터는 이 임시 노드를 가리키도록 만들어집니다. 이런 식으로 노드의 다음 포인터를 플래그로 사용하여 노드가 탐색되었는지 여부를 나타냅니다. 모든 노드는 다음 노드가 임시 노드를 가리키는지 여부를 확인하기 위해 검사됩니다. 루프의 첫 번째 노드의 경우 두 번째로 탐색할 때 이 조건이 참이 되므로 루프가 존재한다는 것을 알 수 있습니다. null을 가리키는 노드를 발견하면 루프가 존재하지 않습니다.

 

시간 복잡도: O(n)

공간 복잡도: O(1)

 

출처 : https://www.geeksforgeeks.org/detect-loop-in-a-linked-list/