Chapter 2 - Problem 1 - Remove Dups

Problem

Write code to remove duplicates from an unsorted linked list. How would you solve this problem if a temporary buffer is not allowed?

Solution

One approach is simply using a hash table to track duplicates.
We simply iterate over the linked list, adding each element to a hash table. When we discover a duplicate element, we remove the element and continue iterating.
How do we remove the element? We keep a pointer in the node preceding the one we are checking and if we have to remove it, we will make the previous node point to the current->next node.
(In the below solution i am using my own linked list, which you can find in Linked Lists).

Solution in C++ using HashSet

template<typename T>
class Node {
    public:
        T data;
        Node* next;
        
        Node() = default;
        Node(const T& value) : data(value), next(NULL) {}
};

template<typename T>
class LinkedList {
    protected:
        Node<T>* head;
};

template<typename T>
class Solution : public LinkedList<T> {
    public:
        void removeDups() {
            std::unordered_set<int> set;
            Node<T>* previous, * current = this->head, * temp;
                       
            while(current != NULL) {
                if(set.find(current->data) == set.end()) {
                    previous = current;
                    set.insert(current->data);
                    current = current->next;
                }
                else {
                    temp = current;
                    previous->next = current->next;
                    current = current->next;
                    delete temp;
                }
            }
        }
};

• Time complexity: $O(N)$ (where N is the size of the list)
• Space complexity: $O(N)$ (because of the set)

Solution in C++ without data structures

We can avoid using the hash set, but the time complexity will be worse ($O(N^2)$), in fact we will have to check all the possible pairs of nodes. The tricky part here is that we do j = j->next only if the two compared values are different, because we have always to have a pointer to the previous node.

EXAMPLE:

template<typename T>
class Node {
    public:
        Node* next;
        T data;

        Node();
        Node(T value);
};

template<typename T>
class LinkedList {
    protected:
        Node<T>* head;
};

template<typename T>
class Solution : public LinkedList<T> {
    public:
        void removeDups() {
            Node<T>* i, * j, * temp;
            for(i = this->head; i != NULL; i = i->next) {
                /* Compare the picked element with rest of the elements */
                for(j = i; j->next != NULL;) {
                    if(i->data == j->next->data) {
                        temp = j->next;
                        j->next = j->next->next;
                        delete temp;
                    }
                    else /* This is tricky */
                        j = j->next;
                }
            }
        }
};

• Time complexity: $O(N^2)$ (where N is the size of the list)
• Space complexity: $O(1)$