1836. Remove Duplicates From an Unsorted Linked List

MediumHash TableLinked List
Leetcode Link

Problem Description

In this problem, we are given the head of a singly linked list. Our task is to find all the values within this linked list that appear more than once. Once we have identified such values, we are then to delete all the nodes containing any of those values from the linked list. The goal is to return the linked list after we’ve made all the necessary deletions.

Intuition

To solve this problem, we need a way to track the frequency of each value present in the linked list. A common and efficient way to do this is by using a hash table, also known as a dictionary in Python, where the keys are the values from the linked list and the corresponding values are the counts of occurrences for each key.

The solution approach involves two main steps. First, we need to traverse the entire linked list to populate the hash table with the correct counts for each value. With the completed hash table, we can then identify which values appear more than once in the linked list.

In the second step, we need to traverse the linked list again and this time, delete nodes that have a count greater than one. This amounts to checking the hash table for the count of the current node's value. If it’s greater than one, it means this value appears multiple times and hence the node should be deleted. We need to carefully update the next pointers of the nodes that are not deleted to ensure we have a properly linked list at the end.

A dummy node is typically used as an anchor to manage the head of the list during deletion, especially in cases where the head node itself might need to be deleted. This dummy node initially points to the head of the list, and we start our iteration from the head while keeping track of the previous node as well. If a node needs to be deleted, we can bypass it by setting the next pointer of the previous node to the current node's next. If a node doesn't need to be deleted, we just move the previous pointer to the current node.

After iterating through the entire list and making necessary deletions, the dummy's next pointer points to the head of the modified list, which we return as the final result.

Learn more about Linked List patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which of these pictures shows the visit order of a depth-first search?

Solution Approach

The implementation of the solution begins with importing Counter from the collections module in Python. The Counter class provides a convenient way to count hashable objects. It is essentially a dictionary where elements are stored as dictionary keys and their counts are stored as dictionary values.

Here’s the step-by-step breakdown of the implementation:

  1. Initialize the Counter: An instance of the Counter is created, which will keep track of the number of occurrences of each element in the list. This is done by the line cnt = Counter().

  2. First Pass - Count the Occurrences: The first traversal of the list occurs here, fulfilling the responsibility of counting occurrences of each value. We continue traversing the list until we reach the end (cur is None). During the traverse, we increment the count of the current value cur.val by doing cnt[cur.val] += 1. This forms the frequency mapping required to identify duplicates.

  3. Setup the Dummy Node and Pointers: A dummy node is created with ListNode(0, head). This node is a placeholder to help manage deletions, especially when the head of the list might need to be deleted. The pre pointer is set to the dummy node and cur is reset to head.

  4. Second Pass - Delete Duplicates: The list is traversed again. This time we have our frequency map ready, and hence for each node, we check if its value appears more than once by verifying cnt[cur.val] > 1. If this condition holds, it means the node is a duplicate and should be removed from the list. To delete the current node cur, we set the next pointer of the previous node pre to the next of the current, effectively bypassing the current node in the list.

    However, if the current node's value does not appear more than once, we need to keep it, and simply update the pre pointer to reference the current node. After either of these checks is performed, we move the current pointer cur to the next node in the list (cur.next).

  5. Return Modified List: After the traversal is complete and we have erased all the nodes that had duplicate values, the list is now modified. The dummy.next holds the reference to the new head of the list, which is returned as the final result.

This algorithm effectively solves the problem using O(n) time complexity for the two traversals and O(n) space complexity for the counter.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which algorithm is best for finding the shortest distance between two points in an unweighted graph?

Example Walkthrough

Let's assume we have a singly linked list with the following values: 3 → 4 → 4 → 2 → 3 → 1 → 2.

Our objective is to identify all values that appear more than once and then remove all nodes containing any such values. Following our solution approach, here’s an example walkthrough:

  1. Initialize the Counter: We start by creating an empty Counter object: cnt = Counter().

  2. First Pass - Count the Occurrences: We traverse the list and count the occurrences of each value. The counter after this pass will look like this: cnt = {3: 2, 4: 2, 2: 2, 1:1}.

  3. Setup the Dummy Node and Pointers: We create the dummy node and set up our pointers. Now, we have dummy -> 3 -> 4 -> 4 -> 2 -> 3 -> 1 -> 2, with pre pointing to dummy and cur pointing to the first node with value 3.

  4. Second Pass - Delete Duplicates: We begin traversing the list again. Here's how we process each node:

    • Look at cur node with value 3, cnt[3] > 1, it is a duplicate, so we update pre.next to cur.next, bypassing the current 3.
    • cur now points to the first 4.
    • Look at cur node with value 4, cnt[4] > 1, it is a duplicate, so we bypass it.
    • cur now points to the second 4, we repeat the above step.
    • cur now points to the first 2, and we bypass it, as cnt[2] > 1.
    • cur now points to the second 3, and we bypass it, as cnt[3] > 1.
    • cur now points to 1, since cnt[1] == 1, it’s not a duplicate, pre is updated to reference this node.
    • cur moves to the second 2, which is bypassed, as cnt[2] > 1.
    • List traversal is now complete.
  5. Return Modified List: At this point of the walkthrough, only the node with value 1 remains, and the updated list points to it. So, the dummy.next is pointing to the node with value 1, which is now the head of our resulting list.

Hence, after the algorithm finishes, the linked list that we return will only contain the node with value 1.

Solution Implementation

1from collections import Counter
2
3# Definition for singly-linked list.
4class ListNode:
5     def __init__(self, val=0, next=None):
6         self.val = val
7         self.next = next
8
9class Solution:
10    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
11        # Create a Counter to keep track of the frequency of each value in the linked list.
12        value_counter = Counter()
13      
14        # Traverse the linked list to populate the counter with the frequencies of each value.
15        current_node = head
16        while current_node:
17            value_counter[current_node.val] += 1
18            current_node = current_node.next
19
20        # Start with a dummy node that points to the head of the list. 
21        # This simplifies edge cases such as deleting the head node.
22        dummy_node = ListNode(0, head)
23      
24        # Initialize two pointers, 'previous' and 'current'. 
25        # 'previous' will lag one behind 'current' as we traverse the list.
26        previous = dummy_node
27        current = head
28      
29        # Traverse the linked list again, this time to remove duplicates.
30        while current:
31            # If the current node's value has a count greater than 1, it's a duplicate.
32            if value_counter[current.val] > 1:
33                # Therefore, skip this node by setting the previous node's next to be the next node.
34                previous.next = current.next
35            else:
36                # If it's not a duplicate, move the 'previous' pointer up to be the 'current' node.
37                previous = current
38            # Move the current pointer to the next node in the list.
39            current = current.next
40      
41        # Return the modified list, starting from the dummy head's next value
42        return dummy_node.next
43
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5    int val;
6    ListNode next;
7    ListNode() {}
8    ListNode(int val) { this.val = val; }
9    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12class Solution {
13    public ListNode deleteDuplicatesUnsorted(ListNode head) {
14        // HashMap to store the frequency of each value in the list
15        Map<Integer, Integer> valueCount = new HashMap<>();
16      
17        // First pass: count the occurrences of each value
18        ListNode current = head;
19        while (current != null) {
20            valueCount.put(current.val, valueCount.getOrDefault(current.val, 0) + 1);
21            current = current.next;
22        }
23      
24        // Dummy node to simplify edge cases at the head of the list
25        ListNode dummy = new ListNode(0, head);
26      
27        // Second pass: remove nodes with values that appear more than once
28        ListNode previous = dummy; // Maintain the node before the current node
29        current = head; // Start again from the head of the list
30        while (current != null) {
31            // If current node's value count is more than 1, skip it
32            if (valueCount.get(current.val) > 1) {
33                previous.next = current.next;
34            } else {
35                // Only move the previous pointer if current node is unique
36                previous = current;
37            }
38            current = current.next; // Move to the next node in the list
39        }
40      
41        // Return the next node of the dummy, which is the new head of the modified list
42        return dummy.next;
43    }
44}
45
1// Definition for a singly-linked list node.
2struct ListNode {
3    int val;
4    ListNode *next;
5    // Constructor to initialize a node with a value and next pointer (default nullptr).
6    ListNode(int x = 0, ListNode *nextNode = nullptr) : val(x), next(nextNode) {}
7};
8
9class Solution {
10public:
11    // Function to delete nodes with duplicate values from an unsorted linked list.
12    ListNode* deleteDuplicatesUnsorted(ListNode* head) {
13        // An unordered map to store the count of each value in the list.
14        unordered_map<int, int> valueCounts;
15      
16        // First pass: count occurrences of each value in the list.
17        for (ListNode* currentNode = head; currentNode != nullptr; currentNode = currentNode->next) {
18            valueCounts[currentNode->val]++;
19        }
20      
21        // Dummy node to facilitate deletion from the head of the list.
22        ListNode dummyNode;
23
24        // Previous node pointer starts from dummy node; current node starts from head.
25        ListNode *previousNode = &dummyNode, *currentNode = head;
26      
27        // Second pass: remove nodes with values that have more than one occurrence.
28        while (currentNode != nullptr) {
29            // If the current value exists more than once, skip the current node.
30            if (valueCounts[currentNode->val] > 1) {
31                previousNode->next = currentNode->next;
32            } else {
33                // Only move the previous node pointer if the current value isn't duplicated.
34                previousNode = currentNode;
35            }
36            // Move to the next node in the list.
37            currentNode = currentNode->next;
38        }
39      
40        // Return the new list starting at the node after the dummy node.
41        return dummyNode.next;
42    }
43};
44
1/**
2 * Function to delete all duplicates from an unsorted singly-linked list
3 * @param {ListNode | null} head - The head of the singly-linked list
4 * @returns {ListNode | null} - The modified list with duplicates removed
5 */
6function deleteDuplicatesUnsorted(head: ListNode | null): ListNode | null {
7    // Map to store the frequency count of each value in the list
8    const frequencyCount: Map<number, number> = new Map();
9  
10    // Count the occurrences of each value by traversing the list
11    for (let currentNode = head; currentNode !== null; currentNode = currentNode.next) {
12        const value = currentNode.val;
13        frequencyCount.set(value, (frequencyCount.get(value) ?? 0) + 1);
14    }
15  
16    // Create a dummy node that points to the head of the list
17    const dummyHead = new ListNode(0, head);
18  
19    // Traverse the list with two pointers, `previousNode` and `currentNode`, connected as: previousNode -> currentNode
20    for (
21        let previousNode = dummyHead, currentNode = head;
22        currentNode !== null;
23        currentNode = currentNode.next
24    ) {
25        // Check the frequency count of the currentNode's value
26        if (frequencyCount.get(currentNode.val)! > 1) {
27            // If count is more than 1, it is a duplicate, remove it by updating the next pointer of the previous node
28            previousNode.next = currentNode.next;
29        } else {
30            // If current value is not a duplicate, move previousNode pointer to the current node
31            previousNode = currentNode;
32        }
33    }
34  
35    // Return the modified list, omitting the dummy head
36    return dummyHead.next;
37}
38
39// ListNode class definition for reference
40class ListNode {
41    val: number;
42    next: ListNode | null;
43
44    constructor(val?: number, next?: ListNode | null) {
45        this.val = (val === undefined ? 0 : val);
46        this.next = (next === undefined ? null : next);
47    }
48}
49
Not Sure What to Study? Take the 2-min Quiz:

How does quick sort divide the problem into subproblems?

Time and Space Complexity

The provided code aims to remove all nodes that have duplicate values from an unsorted singly-linked list. The algorithm works in two passes. The first pass counts the occurrences of each value using a counter (cnt), and the second pass removes nodes with values that occur more than once.

  • Time complexity: The time complexity of the code is O(n) where n is the length of the linked list. This is because each node in the list is visited exactly twice – once while counting the occurrences (first while loop) and once while removing duplicates (second while loop). Both operations for each node take constant time, so the total time is linear with respect to the number of nodes in the list.

  • Space complexity: The space complexity of the code is also O(n). This is due to the use of a counter (cnt) to store the occurrence count for each value present in the linked list. In the worst case, if all n nodes have unique values, the counter will need to store an entry for each value, resulting in O(n) space used.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the most two important steps in writing a depth first search function? (Select 2)


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫