이 튜토리얼에서는 연결 리스트에서 중간 노드를 삭제하는 방법을 배울 것입니다.
문제의 해결책은 간단합니다. 한 번에 한 노드를 이동하는 두 개의 포인터와 한 번에 두 개의 노드를 이동하는 다른 포인터가 있습니다. 두 번째 포인터가 마지막 노드에 도달할 때 첫 번째 포인터는 연결 목록의 중간에 있습니다.
문제를 해결하는 단계를 살펴보겠습니다.
-
연결 목록 노드에 대한 구조체 노드를 작성하십시오.
-
더미 데이터로 연결 리스트를 초기화합니다.
-
연결 리스트를 삭제하는 함수를 작성하세요.
-
연결 목록 헤드 포인터를 사용하여 두 포인터(느림 및 빠름)를 초기화합니다.
-
빠른 포인터가 끝에 도달할 때까지 연결 목록을 반복합니다.
-
느린 포인터를 다음 노드로 이동합니다.
-
빠른 포인터를 다음 노드의 다음 노드로 이동합니다.
-
헤드 포인터 반환
-
-
연결 목록을 인쇄합니다.
예시
코드를 봅시다.
#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
결론
튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.