Loại bỏ các bản sao khỏi danh sách đã sắp xếp II trong C ++

Giả sử chúng ta có một danh sách gồm một số phần tử. Chúng tôi phải loại bỏ tất cả các yếu tố đã xảy ra nhiều lần. Vì vậy, chỉ các phần tử riêng biệt sẽ vẫn còn trong danh sách. Vì vậy, nếu danh sách giống như [1,1,1,2,2,3,5,6,6,7,8], thì đầu ra sẽ là [3,5,7,8], tất cả các phần tử khác đều có mặt nhiều lần.

Hãy để chúng tôi xem các bước -

• Tạo một nút giả với giá trị -1, trước:=NULL, dummyPtr:=dummy
• while head không rỗng
  • nếu phần tiếp theo của phần đầu có mặt hoặc giá trị của phần đầu không giống với giá trị của nút tiếp theo, thì
    • tiếp theo của dummyPtr:=head
    • temp:=next of head, và make next of head là null
    • head:=temp
    • dummyPtr:=tiếp theo của dummyPtr
  • Mặt khác
    • prev:=head, and head:=next of head
    • trong khi head không rỗng và giá trị của head =giá trị của trước
      • prev:=head and head:=next of head
• trả lại hình nộm tiếp theo

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class ListNode{
   public:
      int val;
      ListNode *next;
      ListNode(int data){
         val = data;
         next = NULL;
      }
   };
   ListNode *make_list(vector<int> v){
      ListNode *head = new ListNode(v[0]);
      for(int i = 1; i<v.size(); i++){
         ListNode *ptr = head;
         while(ptr->next != NULL){
            ptr = ptr->next;
         }
         ptr->next = new ListNode(v[i]);
      }
      return head;
   }
   void print_list(ListNode *head){
      ListNode *ptr = head;
      cout << "[";
      while(ptr){
      cout << ptr->val << ", ";
      ptr = ptr->next;
   }
   cout << "]" << endl;
}
class Solution {
   public:
   ListNode* deleteDuplicates(ListNode* head) {
      ListNode* dummy = new ListNode(-1);
      ListNode* prev = NULL;
      ListNode* dummyPtr = dummy;
      ListNode* nextNode;
      while(head){
         if(!head->next || head->val != head->next->val){
            dummyPtr->next = head;
            ListNode* temp = head->next;
            head->next = NULL;
            head = temp;
            dummyPtr = dummyPtr->next;
         } else {
            prev = head;
            head = head->next;
            while(head && head->val == prev->val){
               prev = head;
               head = head->next;
            }
         }
      }
   return dummy->next;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,1,1,2,2,3,5,6,6,7,8};
   ListNode *head = make_list(v);
   print_list(ob.deleteDuplicates(head));
}

Đầu vào

[1,1,1,2,2,3,5,6,6,7,8]

Đầu ra

[3, 5, 7, 8, ]