首页 > 代码库 > 链表 2.1

链表 2.1

2024-07-23 06:48:27   219人阅读

编写代码，移除未排序链表中的重复结点。

进阶

如果不得使用临时缓冲区，该怎么解决？

分析：使用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


联系
我们