[LeetCode] 142. Linked List Cycle II, Medium

1. 문제

• 연결 리스트 head가 주어질 때, 사이클의 시작 노드를 반환하라. 
• pos는 주어지지 않는다.

2. 해결

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let faster = head, slower = head;
    
    while(faster && faster.next) {
        slower = slower.next;
        faster = faster.next.next;
        
        if(slower === faster) {
            faster = head;

            while(faster !== slower) {
                faster = faster.next;
                slower = slower.next;    
            }
            return faster;
        }
    }
    
    return null; 
};

• 141번 문제와 마찬가지로 토끼 거북이 알고리즘을 사용한다.
• 원리는 처음에는 토끼를 2칸, 거북이를 1칸씩 이동하다가 만나는 순간, 토끼를 시작점으로 보내서 1칸 씩 이동시키면 사이클의 시작점에서 만나게 되는 것.
• 채찍피티의 간단한 증명

• 요약하면, 시작점부터 사이클 시작 까지의 거리 = 만난 시점에서 사이클 시작 까지의 거리 이므로, 토끼를 시작점으로 보내서 거북이랑 똑같이 한 칸씩 이동 시키다가 만나는 곳이 사이클의 시작지점이 된다.