本文共 1020 字，大约阅读时间需要 3 分钟。

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?

分析：如何允许使用额外空间，我们可以使用map来记录已经存在的节点，遇到重复的节点就删除；如果不允许使用额外空间，只能每次枚举一个节点，然后遍历完数组，将与这个元素相同的元素删除，时间复杂度为O(n^2)

使用额外空间的方法：

struct Node{	int data;	Node* next;};map
   
     mp;void remove_dup(Node* head){	if(head==NULL) return;	Node* before=head;	Node* cur=before->next;	mp[before->data]=1;	while(cur!=NULL){		if(mp.count(cur->data)){			before->next=cur->next;			Node* del=cur;			cur=cur->next;			delete del;//我认为应该将不用的指针删掉		}else{			before=cur;			cur=cur->next;			mp[before->data]=1;		}	}}
   

void remove_dup(Node* head){	if(head==NULL) return;	Node* left=head;	Node* before=head;	while(left!=NULL){		Node* cur=left->next;		before=left;		while(cur!=NULL){			if(cur->data==left->data){				before->next=cur->next;				Node* del=cur;				cur=cur->next;				delete del;			}			else{				before=cur;				cur=cur->next;			}		}		left=left->next;	}}

转载地址：http://ubyab.baihongyu.com/