LeetCode - 141. Linked List Cycle

leetcode.com/problems/linked-list-cycle/

Linked List Cycle - LeetCode

 

해당 문제를 풀기 위해 몇가지 방법을 생각했었다.

1. 계속해서 다음 Linked List로 next를 해줘서 반복되는 구간을 찾아보고 어느정도 반복된다면 true를 리턴하기

2. 주소값을 저장하는 배열을 만들고 포인터를 만든 뒤 그 포인터를 추적해서, 이전의 주소의 객체를 방문한다면 true를 리턴하기.

 

각각 문제점이 있었는데 

 

1번 같은 경우는 기준을 세우기가 애매했다. '반복되는 구간'이라는 것을 찾기도 힘들뿐만 아니라 '어느정도' 반복된다는 기준을 세우기 또한 모호했기 때문에 기각했다. 

2번 같은 경우는 구글링을 해보니 Java에서는 오브젝트의 주소값을 추적하기가 쉽지 않다고 한다. 그래서 기각했다. 

 

 

결국 풀어낸건 하나는 한번에 하나의 이동을 하는 포인터, 나머지 하나는 한번에 두개의 이동을 하는 포인터를 만들어내고 이 포인터가 겹칠경우 true를 리턴하는 방법을 택했다. 

 

답은 다음과 같이 작성했다. 

 

Answer