C++에서 연결 목록의 중간을 삭제하시겠습니까?

데이터와 다음 노드에 대한 포인터를 포함하는 연결 목록을 먼저 정의합시다.

struct Node {
   int data;
   struct Node* next;
};

다음으로 int 데이터를 매개변수로 사용하고 매개변수 값을 할당한 후 새로 생성된 노드를 반환하는 createNode(int data) 함수를 만듭니다. 노드에 대한 다음 포인터는 null이 됩니다.

Node* createNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->next = NULL;
   return newNode;
}

이제 루트 노드를 사용하는 deleteMiddle(struct Node* head) 함수가 있습니다. 루트 노드가 null이 아닌 경우 중간 값 이전 노드의 다음 값을 중간 값 옆 노드에 할당하고 수정된 헤드인 temphead를 반환합니다.

struct Node* deleteMiddle(struct Node* head){
   if (head == NULL)
      return NULL;
   if (head->next == NULL) {
      delete head;
      return NULL;
   }
   Node* temphead = head;
   int count = nodeCount(head);
   int mid = count / 2;
   while (mid-- > 1) {
      head = head->next;
   }
   head->next = head->next->next;
   return temphead;
}

마지막으로 목록 헤드를 가져와서 목록을 인쇄하는 printList(Node *ptr) 함수가 있습니다.

void printList(Node * ptr){
   while (ptr!= NULL) {
      cout << ptr->data << "->";
      ptr = ptr->next;
   }
   cout << "NULL"<<endl;
}

예

다음의 단일 연결 리스트의 중간을 삭제하는 구현을 보자.

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
Node* createNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->next = NULL;
   return newNode;
}
int nodeCount(struct Node* head){
   int count = 0;
   while (head != NULL) {
      head = head->next;
      count++;
   }
   return count;
}
struct Node* deleteMiddle(struct Node* head){
   if (head == NULL)
      return NULL;
   if (head->next == NULL) {
      delete head;
      return NULL;
   }
   Node* temphead = head;
   int count = nodeCount(head);
   int mid = count / 2;
   while (mid-- > 1) {
      head = head->next;
   }
   head->next = head->next->next;
   return temphead;
}
void printList(Node * ptr){
   while (ptr!= NULL) {
      cout << ptr->data << "->";
      ptr = ptr->next;
   }
   cout << "NULL"<<endl;
}
int main(){
   struct Node* head = createNode(2);
   head->next = createNode(4);
   head->next->next = createNode(6);
   head->next->next->next = createNode(8);
   head->next->next->next->next = createNode(10);
   cout << "Original linked list"<<endl;
   printList(head);
   head = deleteMiddle(head);
   cout<<endl;
   cout << "After deleting the middle of the linked list"<<endl;
   printList(head);
   return 0;
}

출력

위의 코드는 다음 출력을 생성합니다 -

Original linked list
2->4->6->8->10->NULL

After deleting the middle of the linked list
2->4->8->10->NULL