[알고리즘] Linked list에서 Cycle 찾기 (잘못된부분 찾기)

보통 Linked list라는 것은, list들이 이어져서 만들어진다.

Start list와, End list 사이의 list들이 서로서로의 주소를 가리키면서 이어져 있는데,

만약 어떠한 list의 가리키는 주소가, 다음 list가 아닌 이전 list라면,

Linked list의 특성상 무한적으로 돌 수 밖에 없다.

 

이를 Cycle이라고 정의하겠다.

 

그렇다면 이 Cycle을 어떻게 발견을 하고, 수정을 할 것인가?

 

총 6개의 아이디어가 있다.

 

1. Linked Listd를 따라가면서 모든 주소를 배열에 저장.

그 후 정렬을 하며 같은 값이 있는지 확인.

 

이는 가장 흔하게 생각 할 수 있는 방법중 하나이다.

하지만 조금만 생각해보면 무한으로 도는 List에서, 어떻게 모든 주소를 배열에 저장하겠는가? 불가능하다.

 

2. 하나씩 list를 확인하면서, 이전에 나왔던 주소가 다시 나오는 경우를 확인해야함.

이게 가장 현실적인 방법일 것이다. 하지만 O(n^2)의 시간이 걸릴 수도 있다.

 

3. Hash Table, Balance Tree 같은 자료구조를 이용할 수도 있음.

 

4. 지나간 노드들은 마킹하면서 지나감.  마킹이 된 노드에 다시 들어가게 되면 Cycle이라고 생각할 수도 있겠으나,

맨 처음 마킹을 초기화 시켜줘야하는데, Cycle이 있어서 이것도 불가능.

 

 

이제 지금부터가 본격적인 재밌는 알고리즘이다.

 

5. 리스트를 뒤집기

 

기본적으로 이와같은 사진일 것이다.

 

6에서 7이 되고, 7에서 끝나지 않고 다시 3으로 가는형태.

 

그러면, 뒤집는 방법은 어떻게 쓰는건가?

 

1. 현재 노드의 화살표 방향(가리키는 방향)을 반대로 바꿈

2. 현재 노드의 값을 NULL로 만듬.

 

이렇게 모든 List를 따라가면서 적용시키면, 아래와 같은 그림이 되는걸 이해할 수 있을 것이다.

 

이 그림은 결국 돌고돌아 시작노드로 돌아온다는 것을 알 수 있다.

이와 같이 Cycle이 있으면, 뒤집었을 때 시작 노드로 들어온다는 것이다.

 

 

6. 원형 트랙을 속도가 다른 두 사람이 달리는 경우 빠른사람이 반드시 느린 사람을 잡는다.

엄청난 아이디어고 알고리즘이다.

나는 왜 이 생각을 못했는지 이마를 때렸다.

 

1. 두개의 포인터 S와 F를 출발시킴.

2. S는 리스트를 1칸씩, F는 리스트를 2칸씩 전진시킴.

3. S와 F가 같아지는 경우가 있는지 확인.

 

너무나도 당연하고, 논리적이다.

증명이 필요가 없다.

 

그림으로 간단하게 설명하자면 

 

포인터 S : 1 - 2 - 3 - 4 - 5

포인터 F : 2 - 4 - 6 - 3 - 5

 

이와같이 5번만에 5번 노드에서 만나게 되었다.

그럼 Cycle이 있다고 판단할 수 있다.

 

근데 만약에 포인터 S와 F가 정상적으로 끝나버린다면, Cycle이 없다고 판단하면 된다.