141. Linked List Cycle

문제링크: https://leetcode.com/problems/linked-list-cycle/

연결리스트가 사이클이 있는지 확인하는 문제다.

Solution

Set

방문한 노드를 Set에 저장하고 해당 노드를 다시 방문했는지를 확인해 Cycle이 있는지 판별한다.

Algorithm

• cur에 현재 노드를 지정하고 Set에 포인터를 저장한다.
• cur.next로 다음 노드로 이동하고 Set에 접근해 이미 탐색한 곳인지 확인한다.
• 끝까지 돌아 연결리스트가 끝나면 순환은 없다.

var hasCycle = function(head) {
    const mySet = new Set();
    // 순회
    let cur = head;
    while (cur !== null) {
        if (mySet.has(cur)) return true;
        mySet.add(cur);
        cur = cur.next;
    }
    return false;
};

Set에 노드 포인터를 저장하다보니 상대적으로 메모리가 많이 사용되었다. 노드의 개수에 따라 O(n)의 공간복잡도가 소요된다.

Slow & fast pointer

연결리스트를 탐색하는 속도가 다른 두개의 포인터를 사용한다. 만약 Cycle이 존재한다면 두 포인터의 속도가 다르기만 하다면 (대신 모든 노드를 탐색)동일 지점에서 결국 만나게 된다. 두 포인터가 만나는지 혹은 먼저 끝에 도달하는지 여부를 통해 Cycle을 판단할 수 있다.

Algorithm

• slow, fast 노드 포인터를 지정한다.
• fast pointer는 두 노드씩 진행하고 노드의 끝에 도착하면 false를 반환한다.
• 끝에 도착하지 않고 두 개의 포인터가 동일한 노드에서 만나면 true를 반환한다.

var hasCycle = function(head) {
    const mySet = new Set();
    // 순회
    let cur = head;
    let fast = head;
    while (fast && fast.next) {
        cur = cur.next;
        fast = fast.next.next;
        if (cur === fast) return true;
    }
    return false;
};

노드에 따른 공간을 추가로 사용하지 않기 때문에 O(1)의 공간 복잡도를 가지게 된다.