Xóa phần tử trùng lặp từ danh sách đã sắp xếp II trong C++

Giả sử chúng ta có một danh sách các phần tử. Chúng ta phải xóa tất cả các phần tử xuất hiện hơn một lần. Chỉ các phần tử riêng biệt (distinct) mới giữ lại. Ví dụ, danh sách [1,1,1,2,2,3,5,6,6,7,8] sẽ cho kết quả [3,5,7,8], các phần tử khác xuất hiện nhiều hơn một lần.

Các bước thực hiện:

• Tạo nút giả (dummy) giá trị -1, prev := NULL, dummyPtr := dummy
• while head không null
  • nếu next của head không tồn tại hoặc giá trị head khác giá trị next
    • next của dummyPtr := head
    • temp := next của head, đặt next của head null
    • head := temp
    • dummyPtr := next của dummyPtr
  • Ngược lại
    • prev := head, head := next của head
    • while head không null và giá trị head = giá trị prev
      • prev := head và head := next của head
• return next của dummy

Hãy xem 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)); }

Input

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

Output

[3, 5, 7, 8, ]