C++ में सॉर्टेड लिस्ट से डुप्लिकेट हटाएं

समस्या विवरण

मान लीजिए हमारे पास एक सॉर्टेड लिंक्ड लिस्ट है; हमें सभी डुप्लिकेट को हटाना है ताकि प्रत्येक तत्व केवल एक बार दिखाई दे।

उदाहरण

यदि इनपुट है: [1,1,2,3,3,3,4,5,5], तो आउटपुट होगा [1,2,3,4,5]

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें:

• dummy := -inf मान के साथ एक नया नोड बनाएं
• dummy का next := head
• curr = dummy
• जब curr शून्येतर है:
  • next = curr का next
  • जब (next null नहीं है और next का मान curr के मान के समान है):
    • next := next का next
  • curr का next := next
  • curr := next
• dummy का next लौटाएं

C++ कार्यान्वयन

#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(INT_MIN);
        dummy->next = head;
        ListNode *curr = dummy;
        while(curr) {
            ListNode *next = curr->next;
            while(next && next->val == curr->val)
                next = next->next;
            curr->next = next;
            curr = next;
        }
        return dummy->next;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1,1,2,3,3,3,4,5,5};
    ListNode *head = make_list(v);
    print_list(ob.deleteDuplicates(head));
    return 0;
}

इनपुट

{1,1,2,3,3,3,4,5,5}

आउटपुट

[1, 2, 3, 4, 5, ]