# Remove Duplicates from Sorted List II 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;

/**

*/

class ListNode {

// **** elements ****

int           val;

ListNode      next;

// **** constructor ****

ListNode(int x) {

val = x;

}

}

// **** ****

public class Solution {

// **** ****

/**

*/

return new ListNode(val);

} else {

ListNode p = null;

for (p = head; p.next != null; p = p.next) {}

p.next = new ListNode(val);

}

}

/**

* show list

*/

static String show() {

String str    = “”;

str = “null”;

} else {

for (ListNode p = head; p != null; p = p.next) {

str += Integer.toString(p.val) + ” “;

}

}

return str;

}

/**

* delete duplicates from the list

*/

// **** check for empty list ****

}

// **** instantiate map of distinct values ****

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

// **** 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) ****

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 ****

}

// **** delete from middle of list ****

else {

p = p.next;

q.next = p;

}

}

// **** skip this unique node ****

else {

q = p;

p = p.next;

}

}

// **** ****

}

/**

* 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);

}

// **** close scanner ****

sc.close();

// **** display list ****

System.out.println(“list: ” + show());

// **** delete non-distinct elements from the list ****

// **** 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