토끼와 거북이 알고리즘
토끼와 거북이 알고리즘은 LinkedList에서 순환 루프 여부를 확인하고 순환 루프의 시작 노드를 알아내는 데 사용되는 알고리즘이다.
토끼와 거북이 알고리즘의 원리는 다음과 같다.
- 시작지점에 토끼, 거북이로 불리는 노드 포인터를 둔다.
- 거북이는 한 번에 한 칸씩 움직인다.
- 토끼는 한 번에 두 칸씩 움직인다.
- 토끼와 거북이가 같은 노드를 가리킬 때 까지 알고리즘을 수행한다.
- 만약 토끼가 null을 가리키게 되면 순환 루프가 없다는 뜻이다.
- 둘이 같은 노드를 가리키게 되면 순환 루프가 있다는 소리가 된다.
느리게 움직이는 거북이와 빠르게 움직이는 토끼 포인터가 순환 루프에서는 결국 같은 노드를 가리키게 된다는 원리를 이용한 방법이다.
LeetCode 142
https://leetcode.com/problems/linked-list-cycle-ii/
LeetCode 142번 문제는 순환 루프가 없다면 null을 리턴하고 있다면 순환 루프의 시작 노드를 리턴하는 함수를 만드는 문제이다.
위 토끼와 거북이 알고리즘을 사용하면 순환 루프의 시작점도 쉽게 알 수 있다.
알고리즘 원리는 간단한데
- (1) 토끼와 거북이가 서로 만나면 토끼는 움직이지 않고 거북이를 LinkedList의 Head로 옮긴다.
- (2) 토끼와 거북이를 1칸씩 움직인다.
- (3) 토끼와 거북이가 서로 만나게 되면 그 부분이 순환 루프의 시작 노드이다.
어떻게 가능한 걸까?
언뜻 봐서는 이해가 안 간다.
나는 토끼와 거북이가 한 칸씩 움직이면, 만약 거북이가 순환 루프에 들어올 때 토끼와 만나지 못한다면 무한루프에 빠져 알고리즘 수행이 불가능할 것이라고 생각했었다.
하지만 토끼와 거북이 알고리즘에서는 항상 토끼와 거북이가 만나는 것을 보장한다.
설명을 위해선 약간의 수학적 도움이 필요하다.
사용할 변수를 먼저 정의하고 시작하겠다.
D : 시작점(head)에서 순환 루프 시작 노드까지의 거리
M : 순환 루프 시작 노드부터 토끼와 거북이가 만난 지점까지의 거리
R : 토끼와 거북이가 만난 지점부터 순환 루프 시작 노드까지의 거리
이 변수들을 사용해서 거북이와 토끼가 움직인 거리를 정리하면 다음과 같은 수식으로 표현하는게 가능하다.
- 거북이 = D + M
- 토끼 = 2(D + M)
- 토끼는 거북이보다 2배 움직였음으로 2*거북이가 움직인 거리인 2D+2M이다.
여기서 토끼가 이동한 경로를 변수 R을 사용해서 정리해보자.
토끼의 경우 시작노드 -> 순환 루프 시작 노드 -> 거북이와 만난 지점 -> 루프 시작 노드 -> 거북이와 만난 지점 이런 경로로 움직였다. 이를 수식으로 다시 정리하면
- 토끼 = D + M + R + M -> D + 2M + R
- D + 2M + R = 2D + 2M
- R = D
우리는 R이 D와 같다는 것을 수식을 통해서 확인할 수 있다.
따라서 LinkedList의 Head로 움직인 거북이, 토끼와 거북이가 만난 지점부터 1칸씩 움직이는 토끼는 항상 만나게 되어 토끼와 거북이 알고리즘이 성립된다는 것을 확인할 수 있다.
LeetCode 142 풀이
/**
* Definition for singly-linked list.
* class ListNode {
* val: number
* next: ListNode | null
* constructor(val?: number, next?: ListNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
* }
*/
function detectCycle(head: ListNode | null): ListNode | null {
let tuttle : ListNode | null = toNext(head);
let rabbit : ListNode | null = toNext(toNext(head));
while(tuttle!==null&&rabbit !== null){
if(tuttle === rabbit){
break;
}
tuttle = toNext(tuttle);
rabbit = toNext(toNext(rabbit));
}
if(tuttle === null || rabbit === null){
return null;
}
tuttle = head;
while(tuttle!==rabbit){
tuttle=toNext(tuttle);
rabbit=toNext(rabbit);
}
return tuttle;
};
function toNext(node : ListNode | null) : ListNode | null{
if(node === null){
return null;
}
return node.next;
}