TIL 정리_65

원형 연결리스트 
next포인터가 다음 노드를 가리키고
마지막 노드가 이미 살펴본 노드를 가리켜 리스트의 연결 형태가 원의 모양이 된다

원형 연결리스트임을 구분하는 법
1. data 한 개를 기록하고 하나씩 돌아가면서 다시 나타나는지 확인
-> 중복된 data가 있다면 쓸 수 없는 방식이다
2. head를 다시 찾을 때까지 살펴본다
3. 메모리 주소를 비교해본다

->이 중 두번째 방법을 사용하면 좋다

head에서 임시 포인터 t를 선언하고 요소 한 개씩 넘어간다
멈추는 경우 
임시 포인터 t = null; 
t == head || t.next == head 
이 방법의 시간 복잡도 : O(n)

 

시간 복잡도는 tail포인터로 줄일 수 있다
if(tail.next == head) -> O(1)

원형으로 연결되어있지 않고 리스트 내에 다른 곳을 가리키는 경우
어떻게 확인할 수 있을까? 
tail에서 시작해서 tail.next = null인지 확인하면 된다 

임시포인터 head에 2개 선언  
찾지 못할경우 다음 노드로 하나의 임시포인터를 옮긴다 -> 포인터가 2개 필요한 이유이다
임시 포인터 2개를 사용하여 시작점을 잡고 currentSize만큼 떨어진 노드까지 확인한 후 시작점을 다음으로 옮겨 

같은 노드가 나타날 때까지 반복한다.

시간복잡도는  O(n^2)이다