cc150_2.1

gistfile1.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?
 * Algorithm use hashtable to store the existing data, if the hastable  contans the data
 *   means duplicated
 *   O(N)  & O(N)
 * Follow up  How would you solve this problem if a temporary buffer is not allowed?
 * Brote force   
 *  use  two  iterators   one move from  the  root to the end
 *  second  move from first iterated   node to compare with   all the rest  and move  the dupiclated one
 *O(N^2) and O(1)
 * 
 */
 
 public class RemoveDuplicate_2_1 {

	public static void main(String[] args) {
		LinkListNode root = new LinkListNode();
		root.data = 12;
		LinkListNode current = root;
		LinkListNode newNode = new LinkListNode();
		newNode.data = 22;
		current.next = newNode;
		current = current.next;
		newNode = new LinkListNode();
		newNode.data = 25;
		current.next = newNode;
		current = current.next;

		newNode = new LinkListNode();
		newNode.data = 12;
		current.next = newNode;
		current = current.next;
		newNode = new LinkListNode();
		newNode.data = 22;
		current.next = newNode;
		removerDuplicated(root);
		
		current = root;
		while(current!=null){
			System.out.println(current.data);
			current = current.next;
		}
		System.out.println("Follow up test ");
		current = root;
		newNode = new LinkListNode();
		newNode.data = 22;
		newNode.next = current;
		current = newNode;
		newNode = new LinkListNode();
		newNode.data = 25;
		newNode.next = current;
		current = newNode;
		newNode = new LinkListNode();
		newNode.data = 17;
		newNode.next = current;
		current = newNode;
		root = current;
		removeDuplicatedBroteForce(root);
		current = root;
		while(current!=null){
			System.out.println(current.data);
			current = current.next;
		}
	}

	private static void removerDuplicated(LinkListNode node) {
		Hashtable existTable = new Hashtable();

		LinkListNode prev = null;
		
		while (node != null) {
			if (existTable.containsKey(node.data)) {
				System.out.println( "the duplicated " + node.data + " is removed .");
				prev.next = node.next;
			} else {
				existTable.put(node.data, true);
				prev = node;
			}
			node = node.next;
		}

	}
	
	private static void  removeDuplicatedBroteForce(LinkListNode node){
		LinkListNode current = null;
		while(node != null){
			current = node;
			while(current.next!=null){
				if(current.next.data ==node.data ){
					System.out.println( "the duplicated " + node.data + " is removed .");
					if(current.next == null)
						current =null;
					else
							current.next = current.next.next;
				}
				else
					current= current.next;
			}
			node = node.next;
		}
	}
}

class LinkListNode {
	int data;
	LinkListNode next;

	public LinkListNode() {

	}
}