2.1.java

/* 
【解题思路】
1.考虑只有大写字母，用一个flag来保存字符是否出现.此时要考虑空白键，当成第27个字符。
2.考虑所有字符，用HashSet()。
3.不用Buffer，用两个指针iterate。
【时间复杂度】
1.O(n)
2.O(n)
3.O(n^2)
【空间复杂度】
1.O(1)
2.O(n)
3.O(1)
【gist link】	Java
https://gist.github.com/LinyinWu/b3a01634d2f7aa3ea8e8
【test case】
"FOLLOW UP" 	--->	"FOLW UP"
"FOLLOW  P" 	--->	"FOLW P
*/
public class Solution {
	public static void removeDuplicate(Node n) {
		if(n == null)
			return;
		if(n.next == null)
			return;
		int flag = 0;
		flag = flag | (1 << (n.val-'A'));
		
		for(Node runner = n;runner.next != null;) {
			int data = runner.next.val - 'A';
			if(data < 0)
				data = 26;
			if((flag & (1 << data))>0) {
				runner.next = runner.next.next;
				continue;
			}
			else
				flag = flag | (1 << data);
			runner = runner.next;
		}
//		return n;
	}
	public static void main(String[] args) {
		Node n = new Node('F');
		n.next = new Node('O');
		n.next.next = new Node('L');
		n.next.next.next = new Node('L');
		n.next.next.next.next = new Node('O');
		Node c = n.next.next.next.next;
		c.next = new Node('W');
		c.next.next = new Node(' ');
		c.next.next.next = new Node(' ');
		c.next.next.next.next = new Node('P');
		printList(n);
		System.out.println("\nafter:");
		removeDuplicate(n);
		printList(n);
	}
	
	public static void printList(Node n) {
		for(Node run = n;run != null;run=run.next) 
			System.out.print(run.val);
	}
    
}

class Node {
	char val;
	Node next;
	Node(char in) {
		val = in;
		next = null;
	}
}
//////////////////////////////////////////          2		/////////////////////////////////////////
public static void removeDuplicate(Node n) {
		if(n == null)
			return;
		if(n.next == null)
			return;
		HashSet<Character> hs = new HashSet<Character>();
		hs.add(n.val);
		
		for(Node runner = n;runner.next != null;) {
			if(!hs.add(runner.next.val)) {
				runner.next = runner.next.next;
				continue;
			}
			runner = runner.next;
		}
	}
//////////////////////////////////////////          3		/////////////////////////////////////////
public static void removeDuplicate(Node n) {
		if(n == null)
			return;
		if(n.next == null)
			return;
		for(Node current=n;current!=null;current = current.next) {
			for(Node runner = current;runner.next != null;) {
				if(current.val == runner.next.val) {
					runner.next = runner.next.next;
					continue;
				}
				runner = runner.next;
			}
		}
	}