[컴][알고리즘] liked list 에 cycle이 존재하는 지 판단 하는 방법

자바 알고리즘 / 링크드 리스트에 loop / linked list 에 loop 이 있는지 판단하는 방법 / circular linked list

liked list 에 cycle이 존재하는 지 판단 하는 방법

linked list 가 있을 때 이 linked list 가 loop 인지(즉, cycle) 아닌지를 판단하는 방법에 대한 알고리즘을 ref. 1 에서 설명하고 있다.

개인적으로는 내가 지나온 길을 기억하고 있다가, 내가 간 길이 지나온 길과 같으면 있다고 판단하려 했는데, 이 방법은 확실히 큰 linked list 에서 memory 가 많이 필요하게 된다.

ref. 1 에서는 훨씬 간단한 방법을 채용하고 있다. 방법은 이해하고 나면 쉽다. 이 방법을 이해하는데에는 역시 비유가 좋을 듯 하다.

토끼와 거북이가 운동장 트랙을 계속해서 도는 모습을 상상하면 된다. 그러면 둘의 속력이 다르기 때문에 둘은 언젠가 만난다. 이것을 코드로 옮긴 것이 ref. 1 이다.

만약 토끼가 어딘가 막다른 곳에 다다른다면, 그것은 운동장 트랙이 cycle 이 아니라는 이야기가 된다. cycle 이라면 계속해서 몇바퀴를 돌 게 될 테고, 결국 거북이를 만날테니까 말이다.

그래서 "토끼" 는 2개씩 node를 jump 해서 움직이고, "거북이" 는 1개씩 node 를 움직이다.

실질적인 코드는 ref. 1 을 확인하자.

Reference

1. How to Find if Linked List contains Loops or Cycles in Java - Coding Question