Remove duplicates from linked list using hashing

user_11702100 0
Viewed 71

I try to remove duplicates from a linked list using hashing. Not with unordered_map but using a vector for tracking the occurrences. I run a simple test case and I get a result that I don't understand. My code is :

class Solution {
   public:
         Node* removeDuplicates(Node *head) {
             vector<int> vec{10000 , 0};
             auto tmp = head;
             auto tmp2 = tmp;
             while (tmp) {
                 vec[tmp->data]++;
                 cout << "Data : " << tmp->data << " counter " << vec[tmp->data] << "\n";
                 if (vec[tmp->data] > 1) {                     
                     tmp2->next = tmp2->next->next;
                 }
                 tmp2 = tmp;
                 tmp = tmp->next;
             }
             return head;
         }

I tried the following test case 2 3 3 4 6. This are the data for the nodes in the linked list.

And the result I get is this.

Data : 2 counter 1
Data : 3 counter 1
Data : 3 counter 2
Data : 4 counter 1
Data : 6 counter 4114

2 3 4

The actual result should have been

Data : 2 counter 1
Data : 3 counter 1
Data : 3 counter 2
Data : 4 counter 1
Data : 6 counter 1

2 3 4 6
linked-list c++
1 Answers

vector<int> vec{10000, 0}; creates a vector with two elements 10000 and 0, using the constructor that takes an std::initializer_list:

vector(std::initializer_list<T> init, const Allocator& alloc = Allocator());

Most likely you need vector<int> vec(10000, 0);. This will create a vector of 10000 elements, initialized with 0, using

vector(size_type count, const T& value, const Allocator& alloc = Allocator());

The standard reads [over.match.list]:

When objects of non-aggregate class type T are list-initialized such that [dcl.init.list] specifies that overload resolution is performed according to the rules in this subclause, overload resolution selects the constructor in two phases:

  • Initially, the candidate functions are the initializer-list constructors ([dcl.init.list]) of the class T and the argument list consists of the initializer list as a single argument.
  • If no viable initializer-list constructor is found, overload resolution is performed again, where the candidate functions are all the constructors of the class T and the argument list consists of the elements of the initializer list.
user_16251870
Related