C++のソート済みリストIIから重複を削除する

いくつかの要素のリストがあるとします。複数回発生したすべての要素を削除する必要があります。したがって、個別の要素のみがリストに残ります。したがって、リストが[1,1,1,2,2,3,5,6,6,7,8]のような場合、出力は[3,5,7,8]になり、他のすべての要素が存在します複数回。

手順を見てみましょう-

• 値が-1のダミーノードを作成します。prev：=NULL、dummyPtr：=ダミー
• ヘッドがnullではない場合
  • next of headが存在する場合、またはheadの値が次のノードの値と同じでない場合は、
    • ダミーPtrの次：=ヘッド
    • temp：=次の頭、次の頭をnullにする
    • head：=temp
    • dummyPtr：=dummyPtrの次
  • それ以外の場合
    • prev：=head、head：=next of head
    • headがnullでなく、headの値=prevの値
      • prev：=head and head：=next of head
• ダミーの次を返す

理解を深めるために、次の実装を見てみましょう-

例

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

入力

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

出力

[3, 5, 7, 8, ]