首页 > 代码库 > 链表 2.1
链表 2.1
编写代码，移除未排序链表中的重复结点。
进阶
如果不得使用临时缓冲区，该怎么解决？
分析：使用set记录已访问过的值。时间复杂度O(n*logn)，若使用unordered_set或者hash_set，则时间复杂度为O(n)。
1 #include <iostream> 2 #include <fstream> 3 #include <assert.h> 4 #include <set> 5 6 using namespace std; 7 8 struct Node { 9 Node(): val(0), next(0) {}10 Node( int value ): val(value), next(0) {}11 int val;12 Node *next;13 };14 15 void removeDuplicate( Node *node );16 17 int main( int argc, char *argv[] ) {18 string data_file = "./2.1.txt";19 ifstream ifile( data_file.c_str(), ios::in );20 if( !ifile.is_open() ) {21 fprintf( stderr, "cannot open file: %s\n", data_file.c_str() );22 return -1;23 }24 int n = 0, tmp = 0;25 while( ifile >>n ) {26 assert( n >= 0 );27 Node guard, *node = &guard;28 for( int i = 0; i < n; ++i ) {29 node->next = new Node();30 node = node->next;31 ifile >>node->val;32 cout <<node->val <<" ";33 }34 cout <<endl;35 removeDuplicate( guard.next );36 node = guard.next;37 cout <<"result:" <<endl;38 while( node ) {39 Node *next = node->next;40 cout <<node->val <<" ";41 delete node;42 node = next;43 }44 cout <<endl <<endl;45 }46 ifile.close();47 return 0;48 }49 50 void removeDuplicate( Node *node ) {51 if( !node || !node->next ) { return; }52 set<int> nodeSet;53 Node *end = node, *cur = node->next;54 nodeSet.insert( node->val );55 while( cur ) {56 Node *next = cur->next;57 if( nodeSet.count( cur->val ) ) {58 delete cur;59 } else {60 nodeSet.insert( cur->val );61 end->next = cur;62 end = cur;63 }64 cur = next;65 }66 end->next = 0;67 return;68 }
进阶要求不使用临时缓冲区。每次删除后续序列中与当前元素值相同的元素。时间复杂度O(n^2)
1 void removeDuplicate( Node *node ) { 2 if( !node ) { return; } 3 Node *cur = node; 4 while( cur ) { 5 Node *runner = cur; 6 while( runner->next ) { 7 if( runner->next->val == cur->val ) { 8 Node *next = runner->next; 9 runner->next = next->next;10 delete next;11 } else {12 runner = runner->next;13 }14 }15 cur = cur->next;16 }17 return;18 }
测试文件
01121 322 233 2 133 2 342 43 67 25441 52 145 21 245612 421 5645 33 12 421714 54 96 23 45 12 45812 32 34 12 12 12 12 34
链表 2.1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。