Linked Lists in C++: Solving Real-World Challenges

Welcome back! As we advance in mastering interview-oriented problems using linked lists in C++, we will tackle practical algorithmic challenges that reflect real-world scenarios. These exercises are curated to enhance your problem-solving skills with linked lists using C++ as your tool of choice.

Imagine you're managing a digital library where some books are duplicated. Your goal is to identify and remove these duplicates to ensure each title is unique in your catalog.

A straightforward approach would be to compare each book with every other one in a nested loop fashion. While this method is easy to understand, it is inefficient with a time complexity of $O(n^2)$. Processing time increases significantly with larger lists, making this approach impractical for sizable datasets.

To overcome the inefficiencies of the naive approach, we utilize a more effective method using std::unordered_set in C++. This approach keeps track of unique titles as they're encountered, reducing the time complexity to $O(n)$. It is akin to maintaining a checklist, marking off books as they're cataloged, providing rapid lookup to ensure uniqueness.

Let's implement this strategy in C++:

#include <unordered_set>
#include <iostream>

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int x) : value(x), next(nullptr) {}
};

class LinkedListChallenges {
public:
    ListNode* removeDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head; // No duplicates possible.
        }
        
        std::unordered_set<int> seenBooks;
        ListNode* current = head;
        seenBooks.insert(current->value);

        while (current->next != nullptr) {
            if (seenBooks.find(current->next->value) != seenBooks.end()) {
                // Duplicate found, remove it by deleting the node and adjusting the pointer.
                ListNode* duplicateNode = current->next;
                current->next = current->next->next;
                delete duplicateNode;
            } else {
                // Unique entry, add to the set and proceed.
                seenBooks.insert(current->next->value);
                current = current->next;
            }
        }
        return head; // Return modified list without duplicates.
    }
};

This C++ code defines a function to remove duplicate nodes from a linked list using an std::unordered_set to track encountered values. It starts by checking if the list is valid, then iterates through the list, checking if each node's value is already in the set of seen values. If a value is duplicate, the node is skipped by adjusting the pointer, otherwise, it's added to the set for future comparisons.