Remove Duplicates From an Unsorted Linked List

class Solution {
public:
    ListNode* removeDuplicates(ListNode* start) {
        unordered_map<int, int> counts;
        countNodeValues(start, counts);
        return removeHelper(start, counts);
    }

private:
    // Function to count how often each number appears in the list
    void countNodeValues(ListNode* node, unordered_map<int, int>& counts) {
        ListNode* ptr = node;
        while (ptr != nullptr) {
            counts[ptr->val]++;
            ptr = ptr->next;
        }
    }

    // Function to selectively remove nodes with duplicate values
    ListNode* removeHelper(ListNode* node, unordered_map<int, int>& counts) {
        if (!node) {
            return nullptr;
        }

        ListNode* nextNode = removeHelper(node->next, counts);
        node->next = nextNode;

        if (counts[node->val] > 1) {
            return nextNode;
        }

        return node;
    }
};

The provided C++ code defines a solution for removing duplicate values from an unsorted linked list using a class named Solution. This class includes two main components to achieve the removal of duplicates:

• removeDuplicates(ListNode* start): This function initiates the process by first counting how often each number appears in the list using countNodeValues and then uses removeHelper to create a new linked list that includes only unique values.

• countNodeValues(ListNode* node, unordered_map<int, int>& counts): This helper function traverses the linked list, using an unordered map to record the frequency of each value.

• removeHelper(ListNode* node, unordered_map<int, int>& counts): This recursive function traverses the linked list, and using the counts from the map, reconstructs the linked list by skipping nodes that have values appearing more than once.

The overall method involves:

1. Creating a map to count each element's frequency in the linked list.
2. Using a recursive helper function to traverse and rebuild the list without the duplicate entries based on the frequency map.

This approach ensures that all nodes with unique values are retained while duplicates are removed, preserving the order of the first appearances of each value within the original unsorted linked list.

class Solution {

    public ListNode removeUnsortedDuplicates(ListNode root) {
        HashMap<Integer, Integer> valueFrequency = new HashMap<>();
        populateFrequencies(root, valueFrequency);
        return filterDuplicates(root, valueFrequency);
    }

    // Populate frequency map for nodes
    private void populateFrequencies(ListNode root, HashMap<Integer, Integer> valueFrequency) {
        ListNode iterator = root;
        while (iterator != null) {
            valueFrequency.put(
                iterator.val,
                valueFrequency.getOrDefault(iterator.val, 0) + 1
            );
            iterator = iterator.next;
        }
    }

    // Filter nodes with duplicated values based on frequency data
    private ListNode filterDuplicates(ListNode root, HashMap<Integer, Integer> valueFrequency) {
        if (root == null) {
            return null;
        }

        // Process the next node in list
        ListNode nextFiltered = filterDuplicates(root.next, valueFrequency);
        root.next = nextFiltered;

        // Return next node if current is a duplicate
        if (valueFrequency.get(root.val) > 1) {
            return nextFiltered;
        }

        // Return current node if it's unique
        return root;
    }
}

The provided solution implements a method to remove duplicates from an unsorted linked list using Java. This approach utilizes a two-step process:

Step 1:

• Create a frequency map (valueFrequency) of all the values in the linked list using the populateFrequencies method. This method iterates through each node in the list, recording the number of times each value appears.

Step 2:

• Filter out nodes that appear more than once using the filterDuplicates method:
  • This method employs recursion. It filters from the end of the list back to the front to facilitate easy removal of duplicate nodes.
  • It checks the frequency map to determine if a node's value is duplicated.
  • If the current node's value has a frequency greater than one, it is skipped (not included in the resulting list).
  • If the current node's value appears only once, it is retained.

Notable Features:

• The use of a HashMap for frequency counting allows for efficient lookup and modification operations, both of which are constant time on average.
• The solution recursively reconstructs the linked list by excluding duplicate entries, based on the precomputed frequency map.
• This ensures that only nodes with unique values are left in the returned linked list, effectively removing duplicates.

To integrate this solution:

1. Define the ListNode class used in the code.
2. Include methods populateFrequencies and filterDuplicates in your linked list handler class.
3. Use the removeUnsortedDuplicates method to process any unsorted linked list for duplicate removal.

By following this approach, maintain an efficient and structured method to handle duplicates in unsorted linked lists in Java applications.

class Solution:
    def removeDuplicates(self, start: ListNode) -> ListNode:
        counter = {}
        self.accumulate_frequencies(start, counter)
        return self.purge_duplicates(start, counter)

    def accumulate_frequencies(self, start: ListNode, counter: dict):
        node = start
        while node:
            counter[node.val] = counter.get(node.val, 0) + 1
            node = node.next

    def purge_duplicates(self, start: ListNode, counter: dict) -> ListNode:
        if not start:
            return None

        # Process next node in list to remove duplicates 
        cleaned_next_node = self.purge_duplicates(start.next, counter)
        start.next = cleaned_next_node

        # Exclude current node if it's a duplicate
        if counter[start.val] > 1:
            return cleaned_next_node

        # Keep non-duplicate node
        return start

The provided Python code exemplifies a method to remove duplicate values from an unsorted linked list without altering the ordering of nodes that are not duplicates. This operation involves two primary functions within the Solution class:

1. accumulate_frequencies: This function traverses the entire linked list starting from the given node (start). As it progresses, it counts the occurrences of each value using a dictionary named counter.

2. purge_duplicates: This is a recursive function that iterates through the list again. If a node's value has a frequency greater than one (indicating a duplicate), that node is skipped; otherwise, it remains in the list. This function ensures that each unique node appears once, thereby effectively removing duplicates.

Combine these methods for a linked list starting from a given node (start), the removeDuplicates function ensures execution in two main phases: counting frequencies and subsequently purging duplicates based on those frequencies. The result is a modified linked list devoid of any duplicate nodes while preserving the original order of nonduplicate nodes.