Cracking coding interview(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

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 java.util.Hashtable;

public class Solution{
	//brute-force time complexity:O(n^2) space complexity:O(1)
	public static void removeDuplicate1(LinkedList<integer> list){
		for(int i=0;i  list){
		//sort
		Collections.sort(list);	
		if(list.size() >= 2){
			for(int i=0;i  list){
		Hashtable<integer string> hash = new Hashtable<integer string>();
		//lookup hashtable to delete repeat elements
		for(int i=0;i  list){
		Iterator it = list.iterator();
		while(it.hasNext()){
			System.out.print((Integer)it.next()+" ");
		}
		System.out.println();
	}
	public static void main(String[] args){
		LinkedList<integer> list = new LinkedList<integer>();	
		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);
	}
}</integer></integer></integer></integer></integer>

1.brute-force time complexity: O(n^2) space complxity:O(1), 输出元素保持原有顺序

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