[Leetcode] 141. Linked List Cycle - JS

https://leetcode.com/problems/linked-list-cycle/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- linked list의 head가 주어진다.
- linked list 안에 순회가 있는지 판단하라.
- next 포인터를 계속 따라가면 다시 도달할 수 있는 노드가 목록에 있는 경우 연결 목록에는 순환이 있습니다. 
- 내부적으로 pos는 tail의 다음 포인터가 연결된 노드의 인덱스를 나타내는 데 사용됩니다. 
- pos는 매개변수로 전달되지 않습니다.
- 연결리스트에 순환이 있으면 true를 반환합니다. 그렇지 않으면 false를 반환합니다.

제한조건
--------------------
- 연결 리스트 속 node의 갯수는 0 ~ 10^4이다.
- -10^5 <= Node.val <= 10^5
- pos는 -1이거나 유효한 인덱스이다.
- (추가) O(1) 공간 복잡도로 풀 수 있나요?

 

2. 접근 방법

접근방법 - Two pointer
--------------------
head는 Node 객체로, next 포인터가 다음 Node를 가리킨다.
fast 포인터는 2칸씩 이동하고, slow 포인터는 1칸씩 이동한다.

이 과정을 반복하다가 fast와 slow가 만나는 순간이 존재하면 순회가 있다.

마치 토끼와 거북이 경주 처럼 빨리 앞서가는 선수가 뒤쳐지는 선수를 터치하면
순회하는 것처럼 생각할 수 있다.

 

 

3. 코드

var hasCycle = function(head) {
    if (!head || !head.next) {
        return false;
    }

    let fast = head;
    let slow = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            return true;
        }
    }
    return false;
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

내가 직접 연결 리스트를 구현해서 풀어야하는건지? 문제를 정확히 이해하지 못하여 접근 방법도 생각하기 어려웠다.

결국 다른 사람의 풀이를 보고 공부했다.

 

순회인지 아닌지 판단하는 문제이므로,

2칸씩 이동하는 포인터, 1칸씩 이동하는 포인터를 설정하고

두개의 포인터가 동일해지는 순간이 있다면 이는 순회한다고 볼 수 있다.

 

반복문이 종료된다면 next 포인터가 가리키는 node가 없다는 의미이므로 순회하지 않는다고 볼 수 있다.

 

연결 리스트 문제인데, Two pointer로 접근하여 풀 수 있다는 방법이 재밌었다.