面试金典--删除未排序链表重复节点

编写代码，删除未排序链表的重复节点

思路：

hash记录当前节点是否出现过

 1 #include <iostream>
 2 #include <string>
 3 #include <fstream>
 4 #include <map>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <ctime>
 8 #include <bitset>
 9 
10 using namespace std;
11 
12 template<typename T>
13 class Node
14 {
15 public:
16     Node<T> *next;
17     T data;
18 
19     Node(T d):data(d),next(NULL){}
20     void appendToTail(T d)
21     {
22         Node<T> *end = new Node<T>(d);
23         Node<T> *n = this;
24         while(n->next != NULL)
25         {
26             n = n->next;
27         }
28         n->next = end;
29     }
30 };
31 
32 int main()
33 {
34     Node<int> *head = new Node<int>(1);
35     int i;
36     for(i = 2 ; i < 6 ; ++i)
37     {
38         head->appendToTail(i);
39     }
40     //2.1
41     map<int,bool> nodesInList;
42     head->appendToTail(2);
43     map<int,bool>::iterator it;
44     Node<int> *prev = NULL;
45     Node<int> *headOrg = head;
46     while(head != NULL)
47     {
48         it = nodesInList.find(head->data);
49         if(it != nodesInList.end())
50         {
51             prev->next = head->next;
52         }
53         else
54         {
55             nodesInList[head->data] = true;
56             prev = head;
57         }
58         head = head->next;
59     }
60     while(headOrg != NULL)
61     {
62         cout<<headOrg->data<<endl;
63         headOrg = headOrg->next;
64     }
65     return 0;
66 }

扩展：没有缓冲区？那么只能O(N^2)了。上面相当于空间换时间