笔试算法题（28）：删除乱序链表中的重复项 & 找出已经排好序的两个数组中的相同项

             1
            struct
             Node {

             2
            char
             value;

             3         Node* next;
 4};
 5void DeleteDup(Node *head) {
 6if(head==NULL) {
 7                 printf("\nthe list is NULL");
 8return;
 9        }
1011         Node *pre=NULL, *cur=head;
12/**
13         * 设置一个256的bool数组记录char是否
14         * 已经出现
15         * */16bool haveChar[256];
17for(int i=0;i<256;i++)
18                 haveChar[i]=false;
19/**
20         * 如果haveChar对应为true，说明当前节点
21         * 的值已经出现过，则进行删除
22         * 如果haveChar对应为false，说明当前节点
23         * 的值第一次出现，则将其设置为true
24         * */25while(cur!=NULL) {
26/**
27                 * 注意删除节点的情况和不删除节点的情况
28                 * pre和cur的需要不同的处理
29                 * */30if(!haveChar[(cur->value)-‘0‘]) {
31                         haveChar[(cur->value)-‘0‘]=true;
32                         pre=cur;
33                         cur=cur->next;
34                }
35else {
36                         pre->next=cur->next;
37                        delete cur;
38                         cur=pre->next;
39                }
40        }
41}
42int main() {
43         Node *a1=new Node();a1->value=‘a‘;
44         Node *a2=new Node();a2->value=‘d‘;
45         Node *a3=new Node();a3->value=‘s‘;
46         Node *a4=new Node();a4->value=‘d‘;
4748         a1->next=a2;a2->next=a3;
49         a3->next=a4;a4->next=NULL;
5051        DeleteDup(a1);
5253         Node *temp=a1;
54while(temp!=NULL) {
55                 printf("\n%c",temp->value);
56                 temp=temp->next;
57        }
58return0;
59 }

             1
            /*
            *

             2
             * 时间复杂度O(M+N)

             3
             * 
            */
             4
            void FindCommonInt1(int *first, int fl, int *second, int sl) {
 5int ft=0, st=0;
 6while (ft<fl && st<sl) {
 7if(first[ft]>second[st]) {
 8                         st++;
 9                 } elseif(first[ft]<second[st]) {
10                         ft++;
11                 } else {
12                         printf("\n%d",first[ft]);
13                         ft++;st++;
14                }
15        }
16}
17/**
18 * 时间复杂度小于O(NlogM)，其中M不断变小
19 * */20void FindCommonInt2(int *first, int fl, int *second, int sl) {
21int start=0, end=fl-1;
22int s,e,m;
23for(int i=0;i<sl;i++) {
24                 s=start;e=end;
25while(s<=e) {
26                         m=(s+e)/2;
27if(first[m]>second[i]) {
28                                 e=m-1;
29                         } elseif(first[m]<second[i]) {
30                                 s=m+1;
31                         } else {
32                                 printf("\n%d",first[m]);
33                                 start=m+1;
34break;
35                        }
36                }
37        }
38}
39int main() {
40int first[]={1,2,3,4,5,6,10,11,12};
41int second[]={1,4,9,10};
42         FindCommonInt2(first, 9, second, 4);
43return0;
44 }