플로이드의 거북이와 토끼 알고리즘: 연결 목록에서 주기 찾기

오늘algorithm은 연결된 목록의 주기에 관한 것입니다.

Given a linked list, determine if it has a cycle in it. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

예를 들어 입력이 head = [1, 3, 2, 5] 및 pos = 1 인 경우 연결된 목록은 다음과 같습니다.



이 문제는 몇 가지 다른 방법으로 해결할 수 있습니다. 그 중 하나는 해시 또는 세트를 가지고 보이는 모든 노드를 추적하는 것입니다. 노드가 이미 표시되었다면 이것이 주기임을 알 수 있습니다.

플로이드의 거북이와 토끼 알고리즘으로도 알려진 Floyd's Cycle Detection Algorithm을 발견했습니다. 알고리즘의 기본 개념은 연결된 목록에 두 개의 포인터가 있고 하나는 다른 하나(거북이)보다 두 배 빠르게 움직이는 경우(토끼), 교차하면 연결 목록에 순환이 있다는 것입니다. 교차하지 않으면 순환이 없습니다.

이 게시물에서는 이 문제에 대한 해결책을 설명한 다음 예제를 사용하여 작동하는 이유를 설명합니다.

거북이와 토끼와 함께 사이클 찾기

문제에서 주기가 있는지 여부에 대한 부울을 반환하라는 요청을 받습니다. 연결된 목록의 헤드가 주어지고 각 노드에는 값( .val )이 있고 다음 노드는 .next 로 찾을 수 있습니다.

가장 먼저 할 일은 head가 있는지 확인하고 head.next가 있는지 확인하는 것입니다. 둘 다 존재하지 않으면 순환이 없으며 즉시 false를 반환합니다.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  //...
}

다음으로 느리고 빠른 포인터를 시작하겠습니다. 느린 포인터tortoise는 헤드 노드에서 시작됩니다. 빠른 포인터hare는 head.next에서 한 단계 앞서 시작합니다.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  //...
}

이제 토끼가 여전히 null이 아닌 노드를 가리키고 있고 다음 노드가 여전히 null이 아닌 한 계속해서 확인합니다. 따라서 이것은 while 루프를 사용하기에 좋은 위치입니다.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    //...
  }
  //...
}

while 루프에서 가장 먼저 할 일은 거북이와 토끼가 같은 노드를 가리키는지 확인하는 것입니다. 만약 그렇다면 그것은 주기라는 것을 의미하므로 true 를 반환할 수 있습니다.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    //...
  }
  //...
}

그렇지 않으면 거북이와 토끼를 움직일 것입니다. 거북이는 한 번에 한 마디씩 움직이고 토끼는 한 번에 두 마디씩 움직입니다.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    tortoise = tortoise.next;
    hare = hare.next.next;
  }
  //...
}

마지막으로, hare 및/또는 hare.next가 null이기 때문에 while 루프를 계속할 수 없는 경우에는 사이클이 발견되지 않았으므로 false를 반환할 수 있습니다.

function hasCycle(head) {
  if (!head || !head.next) {
        return false
  }
  let tortoise = head;
  let hare = head.next;

  while (hare && hare.next) {
    if (tortoise === hare) {
      return true;
    }
    tortoise = tortoise.next;
    hare = hare.next.next;
  }
  return false;
}

이것이 어떻게 작동하는지 보여주기

이 알고리즘을 설명하는 데 도움이 되도록 관련성이 매우 높은 일부 클립아트를 사용하겠습니다. 연결된 목록부터 시작하겠습니다. 거북이는 머리에서 시작하고 토끼는 머리에서 시작합니다.다음.



hare와 hare.next는 둘 다 null이 아니므로 while 루프에 들어갑니다. 거북이와 토끼는 서로 동등하지 않으므로 둘 다 옮길 것입니다. 거북이는 한 지점을 이동하고 토끼는 두 지점을 이동합니다.



while 루프는 여전히 참입니다. 다시 말하지만 거북이와 토끼는 서로 동등하지 않습니다. 거북이를 하나 위로, 토끼를 두 개의 노드 위로 이동합니다.



while 루프는 여전히 참이지만 이번에는 거북이와 토끼가 서로 같습니다. 이는 사이클이 발견되었음을 의미하므로 true를 반환합니다.

--

의견에 질문이나 다른 방법을 남겨주세요!