Removing duplicates from a linked list (linear time and linear space)

I'm sure there is a way to do this in linear time and constant space, but the solution below is linear on both time and space. Here is the problem: Remove Duplicates From an Unsorted Linked List - LeetCode

1836. Remove Duplicates From an Unsorted Linked List

Medium

Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values.

Return the linked list after the deletions.

 

Example 1:

Input: head = [1,2,3,2]
Output: [1,3]
Explanation: 2 appears twice in the linked list, so all 2's should be deleted. After deleting all 2's, we are left with [1,3].

Example 2:

Input: head = [2,1,1,2]
Output: []
Explanation: 2 and 1 both appear twice. All the elements should be deleted.

Example 3:

Input: head = [3,2,2,1,3,2,4]
Output: [1,4]
Explanation: 3 appears twice and 2 appears three times. After deleting all 3's and 2's, we are left with [1,4].

 

Constraints:

• The number of nodes in the list is in the range [1, 105]
• 1 <= Node.val <= 105

Accepted

427

Submissions

544

The approach:

1/ Have a frequency hash table counting the frequency of each value in the list

2/ To fill out (1), do a linear pass

3/ Do a second pass only adding (to the return list) the terms whose frequency is 1

Code is below. Cheers, ACC.

public ListNode DeleteDuplicatesUnsorted(ListNode head)
{
    Hashtable frequency = new Hashtable();

    for (ListNode n = head; n != null; n = n.next)
    {
        if (!frequency.ContainsKey(n.val)) frequency.Add(n.val, 0);
        frequency[n.val] = (int)frequency[n.val] + 1;
    }

    ListNode retVal = null;
    ListNode temp = null;
    for (ListNode n = head; n != null; n = n.next)
    {
        if ((int)frequency[n.val] == 1)
        {
            if (temp == null)
            {
                temp = new ListNode(n.val);
                retVal = temp;
            }
            else
            {
                temp.next = new ListNode(n.val);
                temp = temp = temp.next;
            }
        }
    }

    return retVal;
}