2.1 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?

2.1.cpp

#include<iostream>
#include<unordered_set>

using namespace std;

struct Node
{
    int data;
    Node *next;
    
    Node(int data, Node *next) {
        this->data = data;
        this->next = next;
    }
    
    ~Node() {}
};

void removeDuplicates1(Node *head)
{
    unordered_set<decltype(head->data)> hash;
    Node *p = head;
    while (head != nullptr) {
        if (hash.count(head->data) > 0) {
            p->next = head->next;
            delete head;
        } else {
            hash.insert(head->data);
            p = head;
        }
        head = p->next;
    }
}

void removeDuplicates2(Node *head)
{
    Node *p = head, *q;
    while (p != nullptr) {
        q = p;
        while (q->next != nullptr) {
            if (q->next->data == p->data) {
                Node *t = q->next;
                q->next = q->next->next;
                delete t;
            } else {
                q = q->next;
            }
        }
        p = p->next;
    }
}

void print(Node * head)
{
    while (head != nullptr) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

void clear(Node *head)
{
    if (head != nullptr) {
        while(head->next != nullptr) {
            Node *t = head->next;
            head->next = t->next;
            delete t;
        }
        delete head;
    }
}

int main(int argc, char *argv[])
{
    Node *list = new Node(0, new Node(1, new Node (2, new Node(1, new Node(2, nullptr)))));
    print(list);
//    removeDuplicates1(list);
    removeDuplicates2(list);
    print(list);
    clear(list);
    return 0;
}