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

문제주소 :https://leetcode.com/problems/linked-list-cycle-ii/

Linked List Cycle II - LeetCode

---

<문제 설명>

Given 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. Note that pos is not passed as a parameter.

Notice that you should not modify the linked list.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1 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: tail connects to node index 0 Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

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

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

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

 

<풀이법>

▒ 한줄 개념: 토끼와 거북이 알고리즘 ▒ 

141번 문제에 이어서, 마찬가지로 단방향 연결 리스트에서 사이클을 찾는 문제이다.

다만, 거기에 사이클의 시작부분을 찾는 것이 추가되었다.

 

우선, 사이클을 판별하는 방식은 토끼와 거북이 알고리즘을 사용하여 해결한다.

사이클인지를 판별하고 나면, 해당 사이클의 진입부분을 찾아야하는데, 이를 위한 방법은 다음과 같다.

 

1) 거북이를 시작지점으로 옮긴다.

2) 토끼와 거북이가 만날때까지 각각 한칸씩 이동한다.

3) 둘이 만나는 지점이 곧 시작지점이다(?!).

 

굉장히 어이없는 소리처럼 보인다. 이유도 이해가 가지 않는다.

하지만 이를 수학 공식으로 풀어보면, 증명이 된다.

 

D : 시작점(head)에서 사이클 시작점까지의 거리
M : 사이클 시작점에서 둘이 만난 지점까지의 거리
R : 둘이 만난 지점부터 다시 사이클 시작점까지의 거리

 

위 변수들을 이용해 각각이 움직인 거리를 정리해보면, 다음과 같다.

거북이 = D + M
토끼 = 2(D + M) = 2D+2M

 

토끼는 거북이의 2배씩 움직이므로, 위의 수식은 쉽게 구할 수 있다.

이때 토끼가 이동한 경로는 시작점 -> 사이클 시작점 -> 둘이 만난 곳 -> 사이클 시작점 -> 둘이 만난 곳이 된다.

이제 토끼가 이동한 경로를 D,M,R을 사용하여 표시를 해보면 다음과 같다.

토끼 = D + M + R + M = D + R + 2M

 

이제 토끼가 이동한 거리를 표현한 수식이 2개가 되었다. 이 두 개를 가지고 R과 D의 관계를 계산할 수 있다.

2D + 2M = D+R+2M 
-> D = R

 

D = R, 즉, "시작점부터 사이클 시작점 까지의 거리"는 "둘이 만난 곳 부터 다시 사이클 시작점까지 가는 거리"와 같다.

이 알고리즘이 옳다는 것을 증명했으므로, 이를 사용해 구현하게 되면 어렵지 않게 문제를 해결할 수 있다.

 

<코드(Javascript)>

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let tor = head, hare = head;
    
    while(hare && hare.next){
        tor = tor.next;
        hare = hare.next.next;
        if(tor === hare){
            tor = head;
            while(tor !== hare){
                tor = tor.next;
                hare = hare.next;
            }
            return tor;
        }
    }
    
    return null;
};

 

 

더 많은 코드 보기(GitHub) : github.com/dwkim-97/CodingTest