Crackingcodinginterview(2.1)去除LinkedList中的重复元素

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? import java.util.LinkedList;import java.util.Iterator;import java.util.Collections;import jav

How would you solve this problem if a temporary buffer is not allowed?

import java.util.LinkedList;
import java.util.Iterator;
import java.util.Collections;
import java.util.Hashtable;

public class Solution{
	//brute-force time complexity:O(n^2) space complexity:O(1)
	public static void removeDuplicate1(LinkedList list){
	for(int i=0;i < list.size()-1;i++)
	for(int j=i+1;j < list.size();)
	if(list.get(i) == list.get(j))
	list.remove(j);
	else
	j++;
	}
	//could't keep order time complexity:O(nlogn) space complexity:O(1)
	public static void removeDuplicate2(LinkedList list){
	//sort
	Collections.sort(list);	
	if(list.size() >= 2){
	for(int i=0;i < list.size()-1;){
	if(list.get(i) == list.get(i+1))
	list.remove(i+1);
	else
	i++;
	}
	}	
	}
	//1.keep order 2.time complexity:O(n) 3.space complexity:O(n): (worst case)
	public static void removeDuplicate3(LinkedList list){
	Hashtable hash = new Hashtable();
	//lookup hashtable to delete repeat elements
	for(int i=0;i < list.size();){
	if(hash.containsKey(list.get(i)))
	list.remove(i);
	else{
	hash.put(list.get(i), "");
	i++;
	}
	}
	}
	private static void printLinkedList(LinkedList list){
	Iterator it = list.iterator();
	while(it.hasNext()){
	System.out.print((Integer)it.next()+" ");
	}
	System.out.println();
	}
	public static void main(String[] args){
	LinkedList list = new LinkedList();	
	list.add(6);list.add(2);list.add(2);list.add(3);
	list.add(1);list.add(4);list.add(2);list.add(3);
	list.add(7);list.add(2);list.add(2);list.add(10);
	
	Solution.printLinkedList(list);
	Solution.removeDuplicate3(list);
	Solution.printLinkedList(list);
	}
}

2.sort：time complexity：O(nlogn) space complexity:O(1), 输出元素为排序后结果

3.hashtable：time complexity：O(n) space complexity:O(n), 输出元素保持原有顺序

类似问题:http://blog.csdn.net/u011559205/article/details/38125405