[JavaScript] leetCode : Linked List Cycle II

1. 문제

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

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 (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

쉽게 말하면 연결 리스트가 사이클을 갖고 있을 때 사이클의 시작 부분의 인덱스를 반환하는 문제이다.

 

 

2. 풀이

const detectCycle = function(head) {

    if(head === null) return null;

    // 두 개의 포인터를 둔다
    let fast = head; // 두 칸씩 
    let slow = head; // 한 칸씩

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

        // 둘이 같아지진다 === 사이클이 존재한다
        // 만난 지점 ==> 사이클의 시작 부분
        if(fast === slow){
            fast = head;
            while(fast !== slow){
                slow = slow.next;
                fast = fast.next;
            }
            return fast;
        }
    }

    return null;    
};

 

 

이 문제가 있는 챕터에서 연결 리스트의 투 포인터 기법에 대해 설명하고 있어서, 읽어 본 후 적용을 시켜보려 했다.

fast에 해당하는 node가 null일 경우가 먼저 떠올라서 조건문을 아래와 같이 두었을 때 런타임 에러가 계속 떠서 결국 다른 사람들의 풀이의 도움을 얻게 되었다. 😇.. 

이 에러의 원인은 모든 노드를 다 탐색하는 것에 시간이 너무 오래 걸린 것으로 추측.. 

while(fast !== null && fast.next !== null) 

 

 

 

3. 토끼와 거북이 알고리즘 

우선 위와 같이 두 개의 속도가 다른 포인터를 사용하여 사이클의 존재여부를 파악하는 것을 토끼와 거북이 알고리즘(플로이드의 토끼와 거북이 알고리즘 Floyd's tortoise and hare)이라고 한다는 사실을 알게되었다.

 

두 개의 포인터가 존재하고 head부터 출발하여 서로 다른 속도로 간다고 하자.

1번 포인터(토끼)와 2번 포인터(거북이). 1번 포인터는 한 개의 노드씩, 2번 포인터는 두 개의 노드씩 간다고 했을 때,

• 사이클이 없다 : 빠른 포인터가 먼저 연결 리스트 끝에 도착했을 경우
• 사이클이 있다 : 빠른 포인터가 한 바퀴 돌고나서 느린 포인터와 만났을 때

이런 방식으로 사이클이 있는지 파악할 수 있다.
그림으로 보면 아래와 같다.

위와 같이 두 포인터가 만나는 지점이 있을 때 사이클이 존재한다고 할 수 있다.

 

4. 런너 기법

while fast && fast.next

그렇다면 위 조건은 무엇인가?
검색을 하다가 파이썬에서 이와 비슷하게 연결리스트를 탐색하기 위해 속도가 다른 두 개의 포인터를 사용하는 것을 런너 Runner 기법이라고 부른다는 것을 알게 되었다. 아마 포인터의 사용 방식이 거의 비슷하여 조건이 같은 것 같다는 추측을 해본다.

빠른 런너(fast)가 연결 리스트 끝에 도달하면 느린 런너(slow)는 정확히 연결 리스트의 중간 지점을 가리키게 된다.

이 기법은 리스트를 끝까지 탐색하지 않고 중간지점까지만 탐색하기 때문에 소요 시간을 많이 줄일 수 있다.

fast 변수가 먼저 리스트의 끝에 도달할 때까지만 참일 수 있도록 하는 것이다.

그런데 위 조건은 노드의 개수가 짝수냐, 홀수냐에 따라 다르다.

 

노드 개수가 짝수인 경우 끝 부분에서 fast는 null 상태이고, slow는 딱 중간 지점까지 왔다.

	1	2	3	4	null
fast					fast
slow			slow

 

노드 개수가 홀수인 경우 fast는 4에 있지만 fast.next는 null 상태이기 때문에 포인터를 이용할 수 없다.

따라서 while fast && fast.next 의 조건 순서도 중요하다.

	1	2	3	2	4	null
fast					fast
slow			slow

 

 

이런 과정을 사이클이 존재 할 때, 두 포인터로 사이클의 시작 위치를 찾을 수 있다.
이 위치가 문제에서 요구하는 인덱스이다.

둘 중 한 포인터를 head에 두고 이번에는 두 포인터 모두 한 칸씩만 움직이도록 한다.

 

한 칸씩 움직이다보면 두 포인터가 만나는 지점이 있다.

이 부분이 바로 사이클 시작지점이다. 

 

이 알고리즘과 관련해서 수학 공식이 있는데, 공식을 좀 더 들여다본 후 이해한 부분을 추가하고.. 다른 방식의 풀이도 존재하는 것 같아 추가해야겠다 😇

 

 

참조한 블로그들.

• 토끼와 거북이 알고리즘에 관하여

https://dev-note-97.tistory.com/277?category=948582 

[리트코드] 142. Linked List Cycle II / Javascript

 

 

• while문의 조건에 관하여

https://blog.naver.com/fblod/222634013592

LeetCode 234: Palindrome Linked List