C++-এ সর্টেড লিস্ট থেকে ডুপ্লিকেট রিমুভ (সिर्फ ইউনিক রাখা)

একটি সর্টেড লিংকড লিস্ট দেওয়া আছে। যেসব এলিমেন্ট একাধিকবার আয়ত্ত হয়েছে সেগুলো রিমুভ করে শুধু ইউনিক এলিমেন্ট রাখতে হবে। যেমন [1,1,1,2,2,3,5,6,6,7,8] হলে আউটপুট [3,5,7,8]।

সমাধানের ধাপ:

• ডামি নোড (-1), prev := NULL, dummyPtr := dummy
• while head is not null
  • যদি head->next নেই বা head->val != head->next->val
    • dummyPtr->next := head
    • temp := head->next, head->next = NULL
    • head := temp, dummyPtr := dummyPtr->next
  • অন্যথায়
    • prev := head, head := head->next
    • while head এবং head->val == prev->val
      • 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; inext != 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, ]