Remove Duplicates From An Unsorted Linked List - Leetcode Solution

Problem Statement: Given the head of a linked list, return the linked list after removing all duplicates.

Approach: To solve this problem, we can use a hash table to keep track of the values which are encountered in the linked list. We can traverse the linked list, and for each node, check if its value is present in the hash table or not. If it is, we remove the current node from the linked list. If not, we add its value to the hash table and move to the next node.

Code:

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        
        if (head == NULL) {
            return NULL;
        }
        
        unordered_set<int> hashSet;
        ListNode* current = head;
        ListNode* prev = NULL;
        
        while (current != NULL) {
            
            //if current node's value already exists in hash table
            if (hashSet.find(current->val) != hashSet.end()) {
                
                //delete current node
                prev->next = current->next;
                delete(current);
                current = prev->next;
                
            } else {    //if current node's value does not exist in hash table
                
                //add the current node's value to hash table
                hashSet.insert(current->val);
                
                //set the prev pointer to current node pointer and move forward
                prev = current;
                current = current->next;
            }
            
        }
        
        return head;
    }
};

Explanation:

• We check if head pointer is NULL, and in that case, we return NULL.
• We create an empty hash set using unordered_set in C++.
• We set current pointer to head and prev pointer to NULL.
• We loop through the linked list using while loop and check for each node if its value is present in the hash set or not, using the find() function of unordered_set.
• If the value is already present in the hash set, we delete the duplicate node by setting prev->next to current->next and deleting current node using delete() function. We then set current pointer to prev->next.
• If the value is not present in the hash set, we insert the value of current node into hash set using insert() function. We then set prev pointer to current node and move forward by changing current pointer to current->next.
• Finally, we return head pointer after all operations are performed on linked list.

Complexity Analysis:

• Time Complexity: O(n), as we need to traverse the entire linked list to identify and remove duplicates.
• Space Complexity: O(n), as we need to store at most n elements in the hash set for an unsorted linked list with n elements.

1