Leetcode 1836. Remove Duplicates From an Unsorted Linked List Solution
Problem
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
Approach
The basic idea is to traverse the linked list and maintain a count of each value in the list. Then, traverse the list again to delete nodes with values that appear more than once.
- Create a dummy node
dummy
, with value 0, and point it to the head of the list. - Create an unordered_map
count
to store the count of each value in the list. - Traverse the linked list and increment the count for each value in the map.
- Traverse the list again with a pointer
curr
, starting at the dummy node:- While
curr->next
is not NULL and its value appears more than once in the count map, delete the node. - Move
curr
to the next node.
- While
- Return the next node of the dummy node as the new head.
Example
Given the input linked list: [1, 2, 3, 2]
After counting the values, the map count
will be: {1: 1, 2: 2, 3: 1}
During the second traversal:
1Initial list: 0 -> 1 -> 2 -> 3 -> 2 2 dummy curr 3 4Updated list: 0 -> 1 -> 3 -> 2 5 dummy curr
The final output will be: [1, 3]
Solution in C++
1class Solution {
2public:
3 ListNode* deleteDuplicatesUnsorted(ListNode* head) {
4 ListNode dummy(0, head);
5 unordered_map<int, int> count;
6
7 for (ListNode* curr = head; curr; curr = curr->next)
8 ++count[curr->val];
9
10 ListNode* curr = &dummy;
11
12 while (curr) {
13 while (curr->next && count.count(curr->next->val) &&
14 count[curr->next->val] > 1)
15 curr->next = curr->next->next;
16 curr = curr->next;
17 }
18
19 return dummy.next;
20 }
21};
Solution in Python
1class Solution:
2 def deleteDuplicatesUnsorted(self, head: Optional[ListNode]) -> Optional[ListNode]:
3 dummy = ListNode(0, head)
4 count = {}
5
6 curr = head
7 while curr:
8 count[curr.val] = count.get(curr.val, 0) + 1
9 curr = curr.next
10
11 curr = dummy
12 while curr:
13 while curr.next and count.get(curr.next.val, 0) > 1:
14 curr.next = curr.next.next
15 curr = curr.next
16
17 return dummy.next
Solution in Java
1class Solution {
2 public ListNode deleteDuplicatesUnsorted(ListNode head) {
3 ListNode dummy = new ListNode(0, head);
4 HashMap<Integer, Integer> count = new HashMap<>();
5
6 ListNode curr = head;
7 while (curr != null) {
8 count.put(curr.val, count.getOrDefault(curr.val, 0) + 1);
9 curr = curr.next;
10 }
11
12 curr = dummy;
13 while (curr != null) {
14 while (curr.next != null && count.get(curr.next.val) > 1) {
15 curr.next = curr.next.next;
16 }
17 curr = curr.next;
18 }
19 return dummy.next;
20 }
21}
Solution in JavaScript
1class ListNode {
2 constructor(val, next) {
3 this.val = val;
4 this.next = next;
5 }
6}
7
8class Solution {
9 deleteDuplicatesUnsorted(head) {
10 const dummy = new ListNode(0, head);
11 const count = new Map();
12
13 let curr = head;
14 while (curr) {
15 count.set(curr.val, (count.get(curr.val) || 0) + 1);
16 curr = curr.next;
17 }
18
19 curr = dummy;
20 while (curr) {
21 while (curr.next && count.get(curr.next.val) > 1) {
22 curr.next = curr.next.next;
23 }
24 curr = curr.next;
25 }
26 return dummy.next;
27 }
28}
Solution in C#
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int val=0, ListNode next=null) {
5 this.val = val;
6 this.next = next;
7 }
8}
9
10public class Solution {
11 public ListNode DeleteDuplicatesUnsorted(ListNode head) {
12 ListNode dummy = new ListNode(0, head);
13 Dictionary<int, int> count = new Dictionary<int, int>();
14
15 ListNode curr = head;
16 while (curr != null) {
17 count[curr.val] = count.GetValueOrDefault(curr.val, 0) + 1;
18 curr = curr.next;
19 }
20
21 curr = dummy;
22 while (curr != null) {
23 while (curr.next != null && count[curr.next.val] > 1) {
24 curr.next = curr.next.next;
25 }
26 curr = curr.next;
27 }
28 return dummy.next;
29 }
30}
In conclusion, the problem of finding and deleting duplicate nodes in an unsorted linked list can be solved using a two-pass approach. First, traverse the list and count the occurrences of each value. Then, traverse the list again, deleting nodes with values that appear more than once. Implementations in C++, Python, Java, JavaScript, and C# have been provided, demonstrating the use of a dummy node, hash data structures, and basic linked list manipulation techniques.