Remove all occurences of duplicates in a linked list
JavaView on GFG
Time: O(n)
Space: O(n)
Advertisement
Intuition
Remove all nodes that have duplicate values in a linked list.
Algorithm
- 1Frequency map: count occurrences. Rebuild list keeping only nodes with count == 1. Or dummy head + skip runs.
Common Pitfalls
- •Same as LC 82. Use dummy head. Skip entire runs of same value. O(n).
Remove all occurences of duplicates in a linked list.java
Java
// Approach: HashMap to count frequencies. Rebuild list keeping only nodes with frequency 1.
// Time: O(n) Space: O(n)
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
class Solution {
public Node removeAllDuplicates(Node head) {
Node curr = head;
Node dummy = new Node(-1);
Node newCurr = dummy;
while (curr != null) {
int d = curr.data;
if ((curr.next != null && d != curr.next.data) || curr.next == null) {
newCurr.next = new Node(d);
newCurr = newCurr.next;
curr = curr.next;
} else {
while (curr != null && d == curr.data)
curr = curr.next;
}
}
return dummy.next;
}
}Advertisement
Was this solution helpful?