[LeetCode / TS] 142. Linked List Cycle II

문제 링크

• https://leetcode.com/problems/linked-list-cycle-ii/

해결 방법

const detectCycle = (head: ListNode | null): ListNode | null => {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
      	// 1
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
          	// 2
            slow = head;
          	// 3
            while (slow !== fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }

  	// 4
    return null;
};

1. slow는 하나의 노드씩, fast는 두 개의 노드씩 건너가면서 slow와 fast가 같아지는 지점을 찾습니다.
2. slow와 fast가 같아지는 지점에서 slow를 다시 head로 보냅니다.
3. slow와 fast를 하나의 노드씩 건너가며 다시 slow와 fast가 같아지는 지점을 찾아 반환해줍니다.
4. 순환하지 않는 경우 null을 반환합니다.

참고

• 플로이드 순환 찾기 알고리즘 증명 관련 블로그 참고