연결리스트에 사이클이 있는지 알아내는 법

담벼락 위의 참새들. Unsplash 에 Saad Chaudhry 님이 올림.

들어가는 말

LeetCode의 이 문제를 풀기 위해서 알아야 하는 알고리즘이었습니다. 플로이드의 토끼와 거북이 알고리즘이라고 하네요.

플로이드의 토끼와 거북이 알고리즘

연결리스트를 탐색하는 두 개의 포인터를 만듭니다.
토끼: 한 번에 두 개씩 노드를 이동
거북이: 한 번에 한 개씩 노드를 이동
토끼와 거북이가 만난다면 사이클이 있다는 뜻입니다.
만났을 때, 거북이를 다시 연결리스트 시작점으로 보냅니다.
토끼의 이동속도를 1로 낮춥니다.
다시 토끼와 거북이가 만난다면 거기가 사이클의 시작점입니다.

이게 왜 됨?

토끼의 속도는 2, 거북이의 속도는 1이므로 거북이의 이동거리의 두 배가 토끼의 이동거리가 됩니다. 이를 이용하면 아래 식을 만들 수 있어요.

사이클이 있는 연결 리스트의 특징을 보면, 어떤 점에서 사이클을 몇 바퀴 돌다도면 결국 제자리로 돌아옵니다. 이를 이용해서 식을 세워보면 아래와 같아요.

사이클 입구에서 거북이 이동거리만큼 이동하면 다시 입구가 나오는데요. 따라서 토끼를 연결리스트 시작점으로 옮긴 뒤 속도를 1로 해서 거북이와 같이 출발시킵니다.

앞서 사이클 진입점은 토끼와 거북이가 만났을 때 거북이가 이동한 거리에서 사이클 진입점 번호(사이클 진입점까지의 거리)를 더한 값과 같았는데요. 거꾸로 생각하면 토끼와 거북이가 만난 위치에서 사이클 진입점까지의 거리와 연결리스트 시작점에서 사이클 진입점까지의 거리가 같다는 말이 됩니다. 따라서 토끼를 출발지로 보내고 거북이랑 이동속도를 똑같이 맞춰준다면 결국 같은 거리를 이동하고 사이클 진입점에서 만나게 되는 것이죠.

간단한 자바스크립트 구현체

const findCycleStartNodeIndex = (startNode) => {
    let tortoise = startNode.next;
    let hare = startNode.next.next;

    while (tortoise !== hare) {
        tortoise = tortoise.next;
        hare = hare.next.next;
    }

    tortoise = startNode;
    while (tortoise !== hare) {
        tortoise = tortoise.next;
        hare = hare.next;
    }

    return tortoise;
};

참고자료

플로이드의 토끼와 거북이 알고리즘(Floyd's Tortoise & Hare Algorithm) / 증명 / leetcode 287번 / 파이썬

저작자표시

방앗간