[LeetCode] Linked List Cycle (JS)

문제

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where the tail connects to. If pos == -1, then there is no cycle in the linked list.

Follow up:
Can you solve it using O(1) (i.e. constant) memory?

입출력 예

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

접근

주어진 linkedlist가 cycle을 가지고 있는지 판단하는 알고리즘이다. pos는 테스트케이스에서 주어진다.
문제의 접근을 못하고 있었는데 스터디 팀원 분이 힌트를 주셨다.
2칸씩 움직이고, 1칸씩 움직이는데 만약 이 두 값이 일치한다면 이는 cycle이 돌고있다라고 생각할 수 있다.

1. while문을 사용한다. 2칸씩 움직이는데 만일 그 값이 없을 경우 while문을 종료한다.
2. twoStep.next가 존재한다면 twoStep엔 twoStep.next.next를 할당하고, oneStep엔 oneStep.next를 할당한다.
3. 사이클이라면 2칸과 1칸 이동은 언젠간 만나게 되어있으니 만일 두 값이 같으면 사이클이라 간주하고 return true
4. while문을 탈출해도 return refalse

풀이

var hasCycle = function(head) {
    if(!head){
        return false;
    }
    
    // list의 각 요소에 next가 존재해야한다.
    // 두칸씩 움직이고 한 칸씩 움직이는 두 고리가 만난다면 그 리스트는 사이클
    let twoStep = head;
    let oneStep = head;
    
    while(twoStep){
        if(!twoStep.next){
            return false;
        }else{
            twoStep = twoStep.next.next; 
            oneStep = oneStep.next;
        }
        if(twoStep === oneStep){
            return true;
        } 
    }
    return false;
};

끝😀