Solution Explanation: Remove Duplicates From an Unsorted Linked List

This problem requires removing nodes from a linked list that contain values which appear more than once in the list. The solution uses a hash table (or dictionary in Python) to efficiently count the occurrences of each value.

Approach:

1. Count Occurrences: The first step is to traverse the linked list and count how many times each value appears. A hash table is ideal for this task because it provides constant-time (O(1)) average-case lookup, insertion, and deletion. We store the value as the key and the count as the value in the hash table.

2. Delete Duplicates: Next, we iterate through the linked list again. This time, we use a dummy node at the beginning of the list to simplify the handling of the head node. As we traverse:

   • If a node's value appears more than once (checked in the hash table), we bypass it by linking the previous node directly to the current node's next node. This effectively removes the current node from the list.
   • If a node's value is unique, we move the previous node pointer (pre) to the current node.

3. Return the Modified List: Finally, we return the next pointer of the dummy node which now points to the head of the modified linked list.

Time Complexity Analysis:

• The first traversal to count occurrences takes O(n) time, where n is the number of nodes in the list.
• The second traversal to delete duplicates also takes O(n) time.
• Therefore, the overall time complexity is O(n).

Space Complexity Analysis:

• The hash table stores the counts of each value. In the worst-case scenario, where all values are unique, the hash table will store n entries.
• Therefore, the space complexity is O(n).

Code Examples (Python, Java, C++, Go, TypeScript):

The provided code examples demonstrate the above approach in several programming languages. Each example follows these steps:

1. Creates a hash table (or equivalent data structure).
2. Counts occurrences of each value in the first list traversal.
3. Creates a dummy node before the head of the list for simpler deletion handling.
4. Iterates through the list, deleting nodes whose values appear more than once in the second traversal.
5. Returns the modified linked list.

Example (Python):

from collections import Counter
 
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
class Solution:
    def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode:
        cnt = Counter()
        cur = head
        while cur:
            cnt[cur.val] += 1
            cur = cur.next
        dummy = ListNode(0, head)
        pre, cur = dummy, head
        while cur:
            if cnt[cur.val] > 1:
                pre.next = cur.next
            else:
                pre = cur
            cur = cur.next
        return dummy.next

The other language examples (Java, C++, Go, TypeScript) implement the same logic using their respective data structures and syntax. They all maintain the same O(n) time and O(n) space complexity.