C++ में क्रमबद्ध लिस्ट से डुप्लिकेट हटाना II (Remove Duplicates from Sorted List II)

मान लीजिए हमारे पास कुछ तत्वों की एक लिस्ट है। हमें उन सभी तत्वों को हटाना है जो एक से अधिक बार आए हैं। ताकि केवल विशिष्ट (distinct) तत्व लिस्ट में रहें। यदि लिस्ट [1,1,1,2,2,3,5,6,6,7,8] है, तो आउटपुट [3,5,7,8] होगा, अन्य सभी तत्व एक से अधिक बार मौजूद हैं।

आइए चरण देखें:

• मान -1 वाला एक डमी नोड बनाएं, prev := NULL, dummyPtr := dummy
• जब तक head null नहीं है:
  • यदि head का next मौजूद है या head का मान अगले नोड के मान के समान नहीं है, तो:
    • dummyPtr का next := head
    • temp := head का next, और head का next null करें
    • head := temp
    • dummyPtr := dummyPtr का next
  • अन्यथा:
    • prev := head, और head := head का next
    • जब तक head null नहीं है और head का मान = prev का मान:
      • prev := head और head := head का next
• dummy का next वापस करें

उदाहरण

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

int 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, ]