package removeduplicatesfromsortedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * Definition for singly-linked list. public class ListNode { int val; ListNode
 * next; ListNode(int x) { val = x; } }
 */
public class Solution {
	Set<Integer> values;

	public ListNode deleteDuplicates(ListNode head) {
		// naive solution
		// use just a set to check if current value has met already
		values = new HashSet<Integer>();
		ListNode previous = null;
		ListNode current = head;
		while (current != null) {
			if (values.contains(current.val)) {
				// current node should be removed
			} else {
				values.add(current.val);
				// pay much attention to pointer shift
				if (previous != null) {
					previous.next = current;
				}
				previous = current;
			}
			current = current.next;
		}
		//pay attention to close the list when using pointer shift strategy
		if (previous != null) {
			previous.next = null;
		}
		return head;
	}
}

class ListNode {
	public int val;
	public ListNode next;

	public ListNode(int x) {
		val = x;
	}
}

@@ -239,31 +239,8 @@
 n %7B%0A
-%09Set%3CInteger%3E values;%0A%0A
 %09pub
@@ -374,40 +374,67 @@
 y%0A%09%09
-values = new HashSet%3CInteger%3E();
+// actually you do not need a set, since the list is sorted
 %0A%09%09L
@@ -524,44 +524,32 @@
 if (
-values.contains(current.val)
+previous != null
 ) %7B%0A%09%09%09%09
 // c
@@ -548,153 +548,72 @@
 %09%09%09%09
-// 
+if (
 current
- node should be removed%0A%09%09%09%7D else %7B%0A%09%09%09%09values.add(current
+.val != previous
 .val)
-;
+ %7B
 %0A%09%09%09%09
-// pay much attention to pointer shift%0A%09%09%09%09if (previous != null) %7B
+%09previous.next = current;
 %0A%09%09%09
@@ -614,37 +614,32 @@
 t;%0A%09%09%09%09%09previous
-.next
  = current;%0A%09%09%09%09
@@ -640,16 +640,26 @@
 ;%0A%09%09%09%09%7D%0A
+%09%09%09%7Delse%7B%0A
 %09%09%09%09prev
@@ -714,16 +714,17 @@
 %09%09%7D%0A%09%09//
+ 
 pay atte

update remove duplicates from sorted list