CCI习题2-1: Remove Duplicates

By | 2012 年 11 月 14 日

如果可用缓存的话,可以建一个hashtable,然后track每一个值有没有出现过;
否则的话,只能O(n2)去跑了(见下面代码)



Remove Duplicates
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?

<br>
代码

<

pre>
//
// main.cpp
// CCI.2.1.RemoveDuplicate
//
// Created by Qiu Xiangyu on 12-11-14.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

include

using namespace std;
struct Node{
int value;
Node *next;
Node(int val):value(val),next(NULL) {;}
};
Node *strToList(string str){
Node *phead = NULL;
Node **ppnext = &phead;
int v = 0;
bool rem = false;
for (int i = 0; i < str.size(); ++i) {
char c = str[i];
if (c >= ‘0’ && c <= ‘9’) {
v = 10 * v + (c – ‘0’);
rem = true;
} else {
*ppnext = new Node(v);
ppnext = &((*ppnext)->next);
v = 0;
rem = false;
}
}
if (rem) {
*ppnext = new Node(v);
}
return phead;
}
void printList(Node *phead) {
cout<<“List : “;
while (phead) {
cout<value;
if (phead->next) {
cout<<“,”;
}
phead = phead->next;
}
cout<<endl;
}

void removeDuplicate(Node *pHead) {
Node *pCur = pHead;
while (pCur) {
Node **ppNext = &pCur->next;
while (*ppNext) {
Node *pNext = *ppNext;
if (pNext->value == pCur->value) {
*ppNext = pNext->next;
delete pNext;
pNext = NULL;
} else {
ppNext = &(*ppNext)->next;
}
}
pCur = pCur->next;
}
}

int main(int argc, const char * argv[])
{
cout<<“Hello\n”;
string instr;
// instr = “1,2,3,4,5,6,7”;
instr = “1,2,2,2,2,2,2,1”;
// instr = “1,1,1,1,1,1,1,1,1”;
// cin>>instr;
Node *phead = strToList(instr);
printList(phead);
cout<<“process…”<<endl;
removeDuplicate(phead);
printList(phead);
cout<<“done”<<endl;
return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注