Write code to remove duplicates from an unsorted linked list. FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?

CC150-2.1.java

/**
 * 2.1 Write code to remove duplicates from an unsorted linked list.
 * FOLLOW UP
 * How would you solve this problem if a temporary buffer is not allowed?
 * 
 * Solution1:
 * @Runtime & spaces
 * runtime: O(n)
 * space:   O(n)
 * 
 * Solution2:
 * @RUNTIME & SPACES
 * runtime: O(n^2)
 * space:   O(1)
*/
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Main so = new Main();
		ListNode a=new ListNode(1);
		ListNode b=new ListNode(2);
		ListNode c=new ListNode(3);
		ListNode d=new ListNode(4);
		ListNode e=new ListNode(3);
		ListNode f=new ListNode(5);
		ListNode g=new ListNode(5);
		a.next=b;
		b.next=c;
		c.next=d;
		d.next=e;
		e.next=f;
		f.next=g;
		so.delDuplicate(a);
	}
	
	//Solution1: use HashSet
	public void delDuplicate(ListNode n){
		if(n==null)
			return;
		HashSet<Integer> hs=new HashSet<Integer>();
		ListNode prev=n;
		hs.add(n.val);
		ListNode next=n.next;
		while(next!=null){
			if(hs.contains(next.val)){
				prev.next=next.next;
				next=next.next;
			}else{
				hs.add(next.val);
				prev=next;
				next=next.next;
			}
		}
		next=n;
		while(next!=null){
			System.out.println(next.val);
			next=next.next;
		}
	}
	
	//Solution2: brute-force
	public void delDuplicate(ListNode n) {
		if (n == null)
			return;

		ListNode current = n;
		while (current != null) {
			ListNode runner = current;
			while (runner.next != null) {
				if (runner.next.val == current.val) {
					runner.next = runner.next.next;
				} else {
					runner = runner.next;
				}
			}
			current = current.next;
		}

		ListNode next = n;
		while (next != null) {
			System.out.println(next.val);
			next = next.next;
		}
	}
}