Xóa giữa danh sách liên kết trong C ++?

Trước tiên, hãy để chúng tôi xác định danh sách được liên kết chứa dữ liệu và con trỏ đến nút tiếp theo.

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

Tiếp theo, chúng ta tạo hàm createNode (int data) lấy dữ liệu int làm tham số và trả về nút mới được tạo sau khi gán giá trị tham số. Con trỏ tới nút tiếp theo sẽ không có giá trị.

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

Bây giờ chúng ta có chức năng deleteMiddle (struct Node * head) lấy nút gốc. Nếu nút gốc không phải là null thì nó chỉ cần gán giá trị tiếp theo của nút trước đó thành giá trị giữa cho nút bên cạnh giá trị giữa và trả về temphead là phần đầu đã sửa đổi.

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;
}

Cuối cùng, chúng ta có hàm printList (Node * ptr) lấy đầu danh sách và in danh sách.

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

Ví dụ

Hãy để chúng tôi xem cách triển khai xóa giữa danh sách được liên kết đơn lẻ sau đây.

#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;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -

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

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