This challenge comes courtesy of LeetCode: https://leetcode.com/problems/remove-duplicates-from-sorted-list-ii/
The challenge is rated medium difficulty. At this time there have been 96,122 accepted solutions from 334,885 submissions. If you decide to tackle the challenge make sure you read it a few times.
On my first pass (which I did not submit) I missed the word ‘distinct’ from the requirements ;o(
On purpose, my solution completely ignores the fact that the list is ‘sorted’. If this would have been work or a contest I would have taken such requirement into consideration :o)
Following is a screen capture of the Eclipse IDE console for the first example:
7
1
2
3
3
4
4
5
main <<< N: 7
main <<< val: 1
main <<< val: 2
main <<< val: 3
main <<< val: 3
main <<< val: 4
main <<< val: 4
main <<< val: 5
list: 1 2 3 3 4 4 5
map: {1=1, 2=1, 3=2, 4=2, 5=1}
list: 1 2 5
The second example is shown as follows:
5
1
1
1
2
3
main <<< N: 5
main <<< val: 1
main <<< val: 1
main <<< val: 1
main <<< val: 2
main <<< val: 3
list: 1 1 1 2 3
map: {1=3, 2=1, 3=1}
list: 2 3
For testing I also used:
8
1
2
3
4
4
3
2
1
main <<< N: 8
main <<< val: 1
main <<< val: 2
main <<< val: 3
main <<< val: 4
main <<< val: 4
main <<< val: 3
main <<< val: 2
main <<< val: 1
list: 1 2 3 4 4 3 2 1
map: {1=2, 2=2, 3=2, 4=2}
list: null
I also used the following:
7
1
2
3
4
3
2
1
main <<< N: 7
main <<< val: 1
main <<< val: 2
main <<< val: 3
main <<< val: 4
main <<< val: 3
main <<< val: 2
main <<< val: 1
list: 1 2 3 4 3 2 1
map: {1=2, 2=2, 3=2, 4=1}
list: 4
My code in Java follows:
import java.util.HashMap;
import java.util.Scanner;
/**
* Definition for singly-linked list.
*/
class ListNode {
// **** elements ****
int val;
ListNode next;
// **** constructor ****
ListNode(int x) {
val = x;
}
}
// **** ****
public class Solution {
// **** ****
static ListNode head = null;
/**
* add node to list
*/
static ListNode add(int val) {
if (head == null) {
return new ListNode(val);
} else {
ListNode p = null;
for (p = head; p.next != null; p = p.next) {}
p.next = new ListNode(val);
return head;
}
}
/**
* show list
*/
static String show() {
String str = “”;
if (head == null) {
str = “null”;
} else {
for (ListNode p = head; p != null; p = p.next) {
str += Integer.toString(p.val) + ” “;
}
}
return str;
}
/**
* delete duplicates from the list
*/
static ListNode deleteDuplicates(ListNode head) {
// **** check for empty list ****
if (head == null) {
return head;
}
// **** instantiate map of distinct values ****
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// **** add the head value to the distinct list ****
map.put(head.val, 1);
// **** populate the rest of the map ****
for (ListNode p = head.next; p != null; p = p.next) {
// **** value in map ****
if (map.containsKey(p.val)) {
int count = map.get(p.val);
map.put(p.val, ++count);
}
// **** value NOT in map ****
else {
map.put(p.val, 1);
}
}
// **** testing ****
System.out.println(“map: ” + map.toString());
// **** traverse the list deleting non-distinct values (count != 1) ****
ListNode p = head;
ListNode q = head;
for (p = head; p != null; ) {
int val = p.val;
int count = map.get(val);
// **** delete this element from the list ****
if (count != 1) {
// **** delete from start of list ****
if (p == head) {
head = head.next;
p = head;
q = head;
}
// **** delete from middle of list ****
else {
p = p.next;
q.next = p;
}
}
// **** skip this unique node ****
else {
q = p;
p = p.next;
}
}
// **** ****
return head;
}
/**
* Test code.
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the number of elements in the list ****
int N = sc.nextInt();
System.out.println(“main <<< N: ” + N);
// **** build the list ****
for (int n = 0; n < N; n++) {
int val = sc.nextInt();
System.out.println(“main <<< val: ” + val);
head = add(val);
}
// **** close scanner ****
sc.close();
// **** display list ****
System.out.println(“list: ” + show());
// **** delete non-distinct elements from the list ****
head = deleteDuplicates(head);
// **** display list ****
System.out.println(“list: ” + show());
}
}
My code could have been optimized. I always like to put clean and easy to 
follow code than optimized versions. If needed, one can optimize code. By not knowing how the code would be used, it is hard to justify short but hard to maintain software.
If you have comments or questions in any post in this blog, please do not hesitate and send me a message. Will reply ASAP and will not mention your name unless you explicitly all me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa