链表 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
", 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 }

测试文件

0

1
1

2
1 3

2
2 2

3
3 2 1

3
3 2 3

4
2 43 67 2

5
441 52 145 21 245

6
12 421 5645 33 12 421

7
14 54 96 23 45 12 45

8
12 32 34 12 12 12 12 34