이번 문제에서는 루프(순환 구조)를 포함할 수 있는 연결 리스트가 주어지며, 우리의 목표는 연결 리스트 내부에 존재하는 루프의 길이를 찾는 것입니다.
문제 설명
연결 리스트에 루프가 존재한다면 루프를 이루고 있는 노드의 개수를 세어 반환하고, 루프가 없다면 -1을 반환해야 합니다.
예시로 이해하기
입력: 아래와 같은 연결 리스트가 주어진 경우,
출력: 8
리스트의 끝 노드가 중간의 특정 노드를 다시 가리켜 8개의 노드로 이루어진 루프가 형성되어 있으므로, 정답은 8이 됩니다.
해결 접근 방법
문제를 해결하려면 먼저 연결 리스트에 루프가 존재하는지부터 확인해야 합니다. 이를 판별하는 대표적인 방법은 플로이드 순환 찾기 알고리즘(Floyd's Cycle Finding Algorithm), 흔히 거북이와 토끼 알고리즘이라고 불리는 기법입니다.
플로이드 순환 찾기 알고리즘의 동작 원리
두 개의 포인터를 사용해 연결 리스트를 순회합니다.
- 느린 포인터(slowPointer): 한 번에 1개 노드씩 앞으로 이동합니다.
- 빠른 포인터(fastPointer): 한 번에 2개 노드씩 앞으로 이동합니다.
리스트에 루프가 존재한다면 빠른 포인터가 느린 포인터를 반드시 추월하게 되고, 결국 두 포인터는 루프 내부의 어느 한 지점에서 만나게 됩니다. 반대로 순회가 종료될 때까지 두 포인터가 만나지 않는다면 루프가 존재하지 않는다는 뜻입니다.
루프 길이 계산하기
루프의 존재가 확인되면, 두 포인터가 만난 지점에서 출발하여 다음 노드를 따라 이동하다가 다시 시작 지점으로 돌아올 때까지 지나치는 노드의 개수를 세면 그 값이 곧 루프의 길이입니다.
C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
// 두 포인터가 만난 지점부터 루프의 길이를 세는 함수
int countLoopNodespoint(struct Node *n) {
int res = 1;
struct Node *temp = n;
while (temp->next != n) {
res++;
temp = temp->next;
}
return res;
}
// 플로이드 알고리즘으로 루프를 검출한 뒤 길이를 반환
int countLoopNode(struct Node *list) {
struct Node *slowPtr = list, *fastPtr = list;
while (slowPtr && fastPtr && fastPtr->next) {
slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
if (slowPtr == fastPtr)
return countLoopNodespoint(slowPtr);
}
return -1; // 루프가 존재하지 않는 경우
}
struct Node *newNode(int key) {
struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}
int main() {
struct Node *head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(3);
head->next->next->next = newNode(4);
head->next->next->next->next = newNode(5);
head->next->next->next->next->next = newNode(6);
head->next->next->next->next->next->next = newNode(7);
// 7번 노드가 2번 노드를 가리키도록 하여 루프 형성
head->next->next->next->next->next->next->next = head->next;
cout<<"루프에 포함된 노드의 개수: "<<countLoopNode(head);
return 0;
}실행 결과
루프에 포함된 노드의 개수: 6
코드 동작 설명
위 예제에서는 1부터 7까지의 값을 가진 노드로 연결 리스트를 구성한 뒤, 마지막 노드(7)가 두 번째 노드(2)를 가리키게 하여 2 → 3 → 4 → 5 → 6 → 7로 이어지는 6개 노드짜리 루프를 만들었습니다. 따라서 프로그램을 실행하면 루프의 길이인 6이 출력됩니다.
복잡도 분석
- 시간 복잡도: O(n) — 연결 리스트를 선형으로 한 번 순회하면 충분하기 때문입니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 포인터 두 개만 사용합니다.