Remove All Nodes With Duplicate Values From a Sorted List
Solve this Problemhead of a sorted singly linked list, remove every node whose value appears more than once, leaving only values that occur exactly once — the result must stay sorted.
This is a stricter cousin of collapsing duplicates: instead of keeping one representative per repeated value, the entire run disappears. The optimal solution walks the list with a dummy node + prev/curr pairDummy Node + Prev/Curr PairA dummy node placed before head lets the very first node be unlinked the same way as any other, without special-casing "head might change." prev always trails the last node confirmed unique, so a discovered run can be skipped by pointing prev.next straight past it.: whenever curr's value matches the value right after it, the entire matching run — however long — is skipped in one relink; otherwise prev simply advances alongside curr.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes in head ≤ 300 - ◆
-100 ≤ node value ≤ 100 - ◆
head is sorted in non-decreasing order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public Node removeAllDuplicateNodes(Node head) { |
| 3 | Node dummy = new Node(0); |
| 4 | dummy.next = head; |
| 5 | Node prev = dummy; |
| 6 | Node curr = head; |
| 7 | while (curr != null) { |
| 8 | if (curr.next != null && curr.next.val == curr.val) { |
| 9 | int dupVal = curr.val; |
| 10 | while (curr != null && curr.val == dupVal) { |
| 11 | curr = curr.next; |
| 12 | } |
| 13 | prev.next = curr; |
| 14 | } else { |
| 15 | prev = curr; |
| 16 | curr = curr.next; |
| 17 | } |
| 18 | } |
| 19 | return dummy.next; |
| 20 | } |
| 21 | } |
| 22 |
dummy1dummy points ahead of head; prev starts at dummy, curr starts at head.
Approach & Solutions
Brute Force — Count Frequencies, Then Rebuild
GoodMake one pass to count how many times each value appears. Then make a second pass, keeping only the nodes whose value occurred exactly once, and build a brand-new list from them. Correct, and it doesn't even need the list to be sorted — but that generality costs a frequency table and a full second array of new nodes.
O(n)O(n)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeAllDuplicateNodes(Node head) {
9 Map<Integer, Integer> freq = new HashMap<>();
10 Node curr = head;
11 while (curr != null) {
12 freq.put(curr.val, freq.getOrDefault(curr.val, 0) + 1);
13 curr = curr.next;
14 }
15 Node dummy = new Node(0);
16 Node tail = dummy;
17 curr = head;
18 while (curr != null) {
19 if (freq.get(curr.val) == 1) {
20 tail.next = new Node(curr.val);
21 tail = tail.next;
22 }
23 curr = curr.next;
24 }
25 return dummy.next;
26 }
27}Optimal — Dummy Node + Prev/Curr, Skip Entire Duplicate Runs
OptimalA dummy node placed before head means even head itself can be removed without a special case. Walk with prev trailing the last node confirmed unique, and curr scanning ahead. Whenever curr's value matches the value right after it, a duplicate run has started: advance curr past every node holding that value, however many there are, then relink prev.next straight to wherever curr landed — the entire run vanishes in one step. Otherwise curr has no duplicate, so prev simply catches up to it.
O(n)O(1)1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public Node removeAllDuplicateNodes(Node head) {
9 Node dummy = new Node(0);
10 dummy.next = head;
11 Node prev = dummy;
12 Node curr = head;
13 while (curr != null) {
14 if (curr.next != null && curr.next.val == curr.val) {
15 int dupVal = curr.val;
16 while (curr != null && curr.val == dupVal) {
17 curr = curr.next;
18 }
19 prev.next = curr;
20 } else {
21 prev = curr;
22 curr = curr.next;
23 }
24 }
25 return dummy.next;
26 }
27}