개요
이 튜토리얼에서는 C++를 사용하여 연결 리스트(Linked List)의 중간 노드를 삭제하는 방법을 알아봅니다.
문제 해결 접근법은 매우 간단합니다. 두 개의 포인터를 활용하는데, 하나는 한 번에 한 노드씩 이동하고(slow), 다른 하나는 한 번에 두 노드씩 이동합니다(fast). 빠른 포인터가 연결 리스트의 마지막 노드에 도달하는 시점이면, 느린 포인터는 정확히 리스트의 중간에 위치하게 됩니다. 이 원리를 이용하면 리스트의 길이를 미리 알지 못해도 한 번의 순회만으로 중간 노드를 찾을 수 있습니다.
문제 해결 단계
연결 리스트의 노드를 나타내는 struct Node 구조체를 작성합니다.
더미 데이터로 연결 리스트를 초기화합니다.
중간 노드를 삭제하는 함수를 작성합니다.
두 개의 포인터(slow와 fast)를 헤드(head) 포인터로 초기화합니다.
fast 포인터가 리스트의 끝에 도달할 때까지 반복합니다.
slow 포인터를 다음 노드로 한 칸 이동시킵니다.
fast 포인터를 다다음 노드로 두 칸 이동시킵니다.
삭제 후 헤드 포인터를 반환합니다.
연결 리스트를 출력하여 결과를 확인합니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
struct Node* deleteMiddleNode(struct Node* head) {
if (head == NULL) {
return NULL;
}
if (head->next == NULL) {
delete head;
return NULL;
}
struct Node* slow_ptr = head;
struct Node* fast_ptr = head;
struct Node* prev;
while (fast_ptr != NULL && fast_ptr->next != NULL) {
fast_ptr = fast_ptr->next->next;
prev = slow_ptr;
slow_ptr = slow_ptr->next;
}
prev->next = slow_ptr->next;
delete slow_ptr;
return head;
}
void printLinkedList(struct Node* node) {
while (node != NULL) {
cout << node->data << " -> ";
node = node->next;
}
cout << "Null" << endl;
}
Node* newNode(int data) {
struct Node* temp = new Node;
temp->data = data;
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);
cout << "Linked list before deleting middle node: ";
printLinkedList(head);
head = deleteMiddleNode(head);
cout << "Linked List after deleting middle node: ";
printLinkedList(head);
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Linked list before deleting middle node: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> Null
Linked List after deleting middle node: 1 -> 2 -> 3 -> 5 -> 6 -> Null
노드가 6개인 경우 중간에 있는 4번 노드가 삭제되고, 나머지 노드들이 올바르게 연결된 것을 확인할 수 있습니다.
복잡도 분석
시간 복잡도: O(n) — 리스트를 한 번만 순회하므로 노드 수에 비례합니다.
공간 복잡도: O(1) — 추가 메모리 없이 포인터 몇 개만 사용합니다.
마무리
투 포인터(Two Pointer) 기법을 활용하면 리스트의 길이를 미리 계산하지 않고도 효율적으로 중간 노드를 찾아 삭제할 수 있습니다. 이 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.