142. Linked List Cycle II

142. Linked List Cycle II

문제

링크드 리스트에 사이클이 존재하면 사이클의 시작노드를 반환하고, 사이클이 존재하지 않는다면 null을 반환하는 문제이다.

테스트 케이스

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1

풀이

플로이드의 토끼와 거북이(Floyd's Tortoise and Hare) 알고리즘

주어진 링크드 리스트에 사이클 유무를 알기 위해서 일명 토끼와 거북이 알고리즘을 사용한다. 👉 참고 한칸씩 이동하는 slow 포인터와 두칸씩 이동하는 fast 포인터, 두개의 포인터를 이용해 사이클을 찾는다.

1. head부터 slow, fast 포인터를 각각 한 칸, 두 칸씩 이동시킨다.
2. 사이클이 있다면 두 포인트는 사이클 안에서 언젠간 만난다.
3. 만난 지점에서 slow 포인터를 다시 head로 보낸다.
4. slow 포인터와 fast 포인터를 같은 속도 (한 칸)로 이동시한다.
5. 다시 만나는 지점이 사이클의 시작점이 된다.
6. 만약 사이클이 없다면 null을 반환한다.

코드

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

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
  let slow = head;
  let fast = head;

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

    if (slow === fast) {
      let n1 = head;
      let n2 = slow;

      while (n1 !== n2) {
        n1 = n1.next;
        n2 = n2.next;
      }

      return n1
    }
  }
  return null;
};

출처

• 플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm)