142. Linked List Cycle II

https://leetcode.com/problems/linked-list-cycle-ii/?envType=study-plan&id=level-1

 

문제

문제 해석

매개변수로, 연결리스트인 head가 주어지고, 순환이 시작되는 노드를 반환해야 한다. 순환이 없다면 null을 반환해야 한다.

pos의 값은 매개변수로 주어지지 않으며, 연결리스트를 수정해서는 안된다.

 

정답코드

let detectCycle = (head) => {
    let fast = head;
    let slow = head;

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

        if(fast === slow)   {
            slow = head;
            while(fast !== slow)    {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    return null;
};

풀이까지의 사고과정

1. 어떻게 출력되고 있을까?

2. 순환이 시작되는 지점의 val 값을 알아낼 수 있으면 되지 않을까?

 

처음에 이걸 생각해 내고, 그럼 head의 값을 모두 배열에 집어넣어 주자라고 생각했다.

근데 1초 뒤에 지금 순환되고 있는데 그러면 무한루프 돌다가 타임아웃 뜨는 거 아냐?라고 생각했는데

CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory : 메모리 할당 한계 사이즈를 넘었을 때 나타나는 에러

비슷했지만, CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory 가 먼저 떴다.

 

3 - 1. 순환소수

어떻게 풀면 좋을지 고민하면서 누워있는데, 갑자기 순환소수가 머릿속에 떠올랐다.

순환소수란?
소수점 아래의 어떤 자리에서부터 0이 아닌 일정한 숫자의 배열이 계속해서 되풀이되는무한소수를 말한다

 

순환소수의 개념을 조금 착안해서 다시 문제를 보자면

Input : head =  [1,2,3,4], pos = 1라고 한다고 했을 때

그러면 반복되는 리스트를 찾을 수 있으면 되겠다.라는 생각이 들었다.

 

3 - 2. 반복되는 배열은 어떻게 찾을 수 있을까?

또또 뒹굴면서 누워있는데 갑지가 머릿속에 떠올랐다. 부분집합. 주어진 연결리스트의 모든 부분집합을 구할 수 있다면 반복되는 리스트를 구할 수 있을 거 같다는 생각이 들었지 만

작성하다가 깨달았다. 애초부터 매개변수로 주어진 head는 이미 순환이 적용된 연결리스트다. 그렇기 때문에 부분집합이 셀 수 없을 정도로 많이 나온다.

 

다른 방법은 없을까?

 

4. "?"

고민하면서 물도 마시고 화장실도 갔다 오는 길에 뭔가 떠올랐다. 최소공배수 

최소공배수는, 두 수에 공통적으로 존재하는 배수를 말한다.

이걸 응용해서 하나는 2개의 노드씩, 하나는 1개의 노드씩 이동하다가 동일한 노드를 만나게 된다면?

그림으로 보자

 

head를 가리키고 있다가

한번 이동했을 때

두 번째 이동했을 때

4번 방법 꽤 괜찮은 거 같다.

 

그럼 이제

 

코드 작성

1. 

이 코드가 실패한 이유는 당연하다. 처음에 fast, slow 둘 다 head로 해놨는데, 루프문 조건을 fast와 slow가 동일하지 않다고 했으니...

2. 

왜 next의 next가 존재함에도 불구하고 안 읽히는 거지? 아는 분은 제게 부디 대답을,,,,,,,,,,,,,,,,,,

console.log(fast)의 결과

3. 

fast.next.next가 읽히지 않아, 루프문 조건식에다 fast.next를 의도적으로 선언해 줬다.

(fast나 fast.next나 결국은 순환이라 null을 만날 일이 없을 텐데 라는 생각이 머릿속에 계속 맴돌았는데...)

잘될 줄 알았는데 틀렸다.

그림을 테스트케이스에 맞춰 다시 한번 살펴보자

이러니까 틀렸지...

 

4. 그럼 동일한 노드를 가리킨 시점에서부터 

이 상태에서 fast = fast.next, slow = slow.next를 찍으면 val = 2인 노드만 나올 거 기 때문에 

 

slow = head로 초기화해준 후 (fast는 초기화 X)

fast = fast.next, slow = slow.next를 해준다면 둘 다 2를 가리킬 거라는 생각이 들었다

이에 맞춰 코드를 수정해 줬다.

5. 

아 진짜 왜

 

인 줄 알았으나, 테스트 케이스에 실수가 있었나보다.

어쨋든 통과!

 

참고자료

-순환소수

https://ko.wikipedia.org/wiki/%EC%88%9C%ED%99%98%EC%86%8C%EC%88%98