C++의 정렬된 목록 II에서 중복 제거

몇 가지 요소의 목록이 있다고 가정합니다. 한 번 이상 발생한 모든 요소를 ​​제거해야 합니다. 따라서 고유한 요소만 목록에 남습니다. 따라서 목록이 [1,1,1,2,2,3,5,6,6,7,8]과 같으면 출력은 [3,5,7,8]이 되고 다른 모든 요소는 존재합니다. 한 번 이상.

단계를 살펴보겠습니다 -

• 값이 -1인 더미 노드 생성, 이전 :=NULL, dummyPtr :=더미
• head가 null이 아닌 동안
  • head의 다음이 존재하거나 head의 값이 다음 노드의 값과 같지 않으면
    • dummyPtr 옆:=머리
    • temp :=헤드의 다음, 헤드의 다음을 null로 설정
    • 머리 :=온도
    • dummyPtr :=dummyPtr의 다음
  • 그렇지 않으면
    • prev :=head, head :=head의 다음
    • head가 null이 아니고 head의 값 =prev의 값인 동안
      • prev :=head 및 head :=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, ]