36 lines
793 B
C++
36 lines
793 B
C++
#include "chapter2.hpp"
|
|
#include <unordered_map>
|
|
|
|
/*
|
|
Remove Dups!
|
|
Write code to remove duplicates from an unsorted linked list.
|
|
FOLLOW UP
|
|
How would you solve this problem if a temporary buffer is not allowed?
|
|
*/
|
|
|
|
void remove_dups(DopeLinkedList* ll){
|
|
DopeNode* prev = ll->GetHead();
|
|
DopeNode* node = ll->GetHead();
|
|
DopeNode* tmp = NULL;
|
|
std::unordered_map<int, int> dup_tracker;
|
|
int iter_cnt = 0;
|
|
|
|
while(node->GetNext() != NULL){
|
|
if(dup_tracker.count(node->GetData())){
|
|
// remove node
|
|
prev->SetNext(node->GetNext());
|
|
tmp = node;
|
|
node = node->GetNext();
|
|
tmp->Reset();
|
|
} else {
|
|
dup_tracker[node->GetData()] += 1;
|
|
node = node->GetNext();
|
|
if (iter_cnt != 0){
|
|
prev = prev->GetNext();
|
|
}
|
|
}
|
|
|
|
iter_cnt++;
|
|
}
|
|
}
|