_1836. Remove Duplicates From an Unsorted Linked List.md

1836. Remove Duplicates From an Unsorted Linked List

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

---

First completed : July 08, 2024

Last updated : July 08, 2024

---

Related Topics : Hash Table, Linked List

Acceptance Rate : 74.72 %

---

This question is extremly similar to Question 82 and I was able to reuse my code for that instance.

Update on July 7th, 2024

This question ended up being the Weekly Premium for this week, and as such I simply had to resubmit the code.

I also decided to redo the question but in Java to ensure that I was confident in it.

The m1836 - orig.py copy was my first attempt from way back, and the java Weekly Premium version is my new attempt.

---

Solutions

• m1836 - orig.py
• m1836 Weekly Premium July 7th.java

Python

m1836 - orig.py

# 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 = defaultdict(int)
        curr = head
        while curr :
            cnt[curr.val] += 1
            curr = curr.next

        dummy = ListNode()
        dummy.next = head
        dummyHolder = dummy

        while dummy and dummy.next :
            while dummy.next and cnt[dummy.next.val] > 1 :
                dummy.next = dummy.next.next
            dummy = dummy.next
        
        return dummyHolder.next

Java

m1836 Weekly Premium July 7th.java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicatesUnsorted(ListNode head) {
        HashMap<Integer, Integer> counts = new HashMap<>();
        
        ListNode curr = head;
        while (curr != null) {
            counts.put(curr.val, counts.getOrDefault(curr.val, 0) + 1);
            curr = curr.next;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode output = dummy;

        while (dummy != null) {
            while (dummy.next != null && counts.get(dummy.next.val) > 1) {
                dummy.next = dummy.next.next;
            }
            dummy = dummy.next;
        }
        return output.next;
    }
}