Cycle finding 알고리즘. 주어진 LinkedList 가 cycle 인지 알아내기 위한 알고리즘으로, 2 point 혹은 slow, fast approcah 라 한다.
이러한 문제를 해결하는 방법으로 Floyd’s Cycle-Finding 알고리즘에 대해 정리를 해두려고 한다.
다음과 같은 Linked List 가 주어졌을때 cycle 인지 어떻게 알까?
주어진 LinkedList
두 개의 pointer 를 정의한다.
•
slow, fast pointer
◦
slow 는 한 칸씩 이동한다.
◦
fast 는 두 칸씩 이동한다.
오른쪽 표는 위 로직을 구성했을때 LinkedList 를 순회하면서 거쳐간 Node 이다.
seq | slow | fast |
0 | 3 | 3 |
1 | 1 | -5 |
2 | -5 | 6 |
3 | 7 | -5 |
4 | 6 | 6 |
4번째 순서에서 slow 포인터와 fast 포인터가 만나게된다.
이렇게 만나는 경우 cycle 이 존재한다고 볼 수 있다.
그렇다면 cycle이 존재하지 않는 경우는?
위와 같은 LinkedList 가 주어졌다고 가정할때 cycle 의 존재 여부를 위의 알고리즘으로 파악할 수 있을까?
seq | slow | fast |
0 | 3 | 3 |
1 | 1 | -5 |
2 | -5 | 6 |
3 | 7 | Null |
4 | 6 | Null |
이와 같이 표가 만들어진다.
위의 표와의 차이점은 fast pointer 에서 Null 이 발생 되었다는 것이다.
이와 같은 알고리즘은 코드로 구현하면 다음과 같다.
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
if (slow == fast) {
return true;
}
slow = slow.next;
fast = fast.next.next;
}
return false;
}
}
Java
복사
Cycle 의 존재 여부를 Floyd 의 알고리즘으로 해결한다.
while 문의 조건이 fast 가 null 이 아니고(and), fast 의 다음도 null 이 아닌 경우에만 while 이 실행된다.
while 문 안에서 slow, fast 가 같다면 true 를 반환하여 cycle 이 존재함을 반환한다.
while 문 밖으로 나오게 되면(LinkedList 의 next 가 존재하지 않으므로) cycle 이 존재하지 않는다.
별도의 자료구조를 만들 필요도 없어서 memory 에도 이득을 볼 수 있다.
