[TOC]

7-1 两个有序链表序列的交集

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2的交集新链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出两个输入序列的交集序列，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1
2
1 2 5 -1
2 4 5 8 10 -1

输出样例:

1
2 5

代码实现：

这段程序的通过难点主要在于关心交集为空的情况，分为两种：

①集合1和集合2之间最少有一个为空

②集合1和集合2不是空集，但是相同元素的个数为0

针对第二种情况，只需要设置一个计数器i=0，当集合1的元素==集合2的元素时，i++，若运行到循环结束，i仍然为0，说明得到的交集为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

int creatlist(LinkList &S1,LinkList &S2){
    LNode *p1,*p2,*r;
    p1=S1,p2=S2;
    r=S1;
    while(1){
        p1=new LNode;
        cin>>p1->data;
        if(p1->data==-1) break;//在链表录入-1前结束循环
        p1->next=NULL;
        r->next=p1;
        r=p1;
    }//尾插法
    r=S2;//循环利用变量r
    while(1){
        p2=new LNode;
        cin>>p2->data;
        if(p2->data==-1) break;
        p2->next=NULL;
        r->next=p2;
        r=p2;
    }//尾插法
    return 1;
}

int jiaoji(LinkList &S1,LinkList &S2){
    LNode *S3,*p3,*r;
    LNode *p1,*p2;
    p1=S1->next,p2=S2->next;
    S3=new LNode;
    S3->next=NULL;
    r=S3;
    int i=0;//统计S3的长度
    if(S1==NULL || S2==NULL){
        cout<<"NULL";
        return 0;
    }
    while(p1&&p2){
        if(p1->data==p2->data){
            i++;
            p3=new LNode;
            p3->data=p1->data;
            p3->next=NULL;
            r->next=p3;
            r=p3;
            p1=p1->next;
            p2=p2->next;
        }else if(p1->data>p2->data) p2=p2->next;
        else if(p1->data<p2->data) p1=p1->next;
    }
    if(i==0) {
        cout<<"NULL";
        return 0;
    }
    p3=S3->next;//p3重新退回头结点指向的位置
    while(p3->next){
        cout<<p3->data<<" ";
        p3=p3->next;
    }cout<<p3->data;
    return 1;
}

int main(){
    LNode *S1,*S2;
    S1=new LNode;
    S1->next=NULL;
    S2=new LNode;
    S2->next=NULL;
    creatlist(S1,S2);
    jiaoji(S1,S2);
    return 0;
}
测试点 提示 内存(KB) 用时(ms) 结果 得分
0 样例等价 300 2 答案正确 2 / 2
1 交集为空 488 3 答案正确 2 / 2
2 完全相交 276 3 答案正确 2 / 2
3 其中一个序列完全属于交集 492 2 答案正确 2 / 2
4 其中一个序列为空 492 3 答案正确 2 / 2
5 大规模数据 31864 291 答案正确 2 / 2

7-2 两个有序链表序列的合并

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1
2
1 3 5 -1
2 4 6 8 10 -1

输出样例:

1
1 2 3 4 5 6 8 10

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

int creatlist(LinkList &S1,LinkList &S2){
    LNode *p1,*p2,*r;
    r=S1;
    while(1){
        p1=new LNode;
        cin>>p1->data;
        if(p1->data==-1) break;
        p1->next=NULL;
        r->next=p1;
        r=p1;
    }
    r=S2;
    while(1){
        p2=new LNode;
        cin>>p2->data;
        if(p2->data==-1) break;
        p2->next=NULL;
        r->next=p2;
        r=p2;
    }
    return 1;
}
int bingji(LinkList &S1,LinkList &S2){
    LNode *p1,*p2;
    p1=S1->next,p2=S2->next;
    LNode *S3,*p3;
    S3=S1;
    p3=S3;
    while(p1&&p2){
        if(p1->data<=p2->data){
            p3->next=p1;
            p3=p1;
            p1=p1->next;
        }else{
            p3->next=p2;
            p3=p2;
            p2=p2->next;
        }
    }
    p3->next=p1?p1:p2;
    //三目运算符，等价于
    //if(p1)p3->next=p1; 
    //else if(p2)p3-a.next=p2;
    
    free(S2);//释放头结点
    p3=S3->next;
    if(p3==NULL){
        cout<<"NULL";
        return 0;
    }
    while(p3->next){
        cout<<p3->data<<" ";
        p3=p3->next;
    }cout<<p3->data;
    

    return 1;

}
int main(){
    LNode *S1,*S2;
    S1=new LNode,S2=new LNode;
    S1->next=NULL,S2->next=NULL;
    creatlist(S1,S2);
    bingji(S1,S2);
    return 0;
}


测试点 提示 内存(KB) 用时(ms) 结果 得分
0 样例等价 400 2 答案正确 5 / 5
1 有并列 288 2 答案正确 5 / 5
2 链表为空 400 2 答案正确 5 / 5
3 大规模输入 46228 370 答案正确 5 / 5

7-3 两个有序链表合并（新表不含重复元素）

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。
要求S3中没有重复元素。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，要求链表中没有重复元素。数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

在这里给出一组输入。例如：

1
2
1 3 3 5 8 -1
2 3 4 6 8 10 -1

输出样例:

在这里给出相应的输出。例如：

1
1 2 3 4 5 6 8 10

代码实现：

这一段程序相对于上一题的难点在于：

①要求并集中的元素不可重复，因此必须细致的分类讨论集合1大于、小于或等于集合2，以及集合1和集合2的值分别等不等于并集已存在的值

②设置了测试点：一个是空表，一个只有两个相同的元素。如果不加上p3->next=NULL，程序会报错

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
using namespace std;
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,*LinkList;

int creatlist(LinkList &S1,LinkList &S2){
    LNode *p1,*p2,*r;
    r=S1;
    while(1){
        p1=new LNode;
        cin>>p1->data;
        if(p1->data==-1) break;
        p1->next=NULL;
        r->next=p1;
        r=p1;
    }
    r=S2;
    while(1){
        p2=new LNode;
        cin>>p2->data;
        if(p2->data==-1) break;
        p2->next=NULL;
        r->next=p2;
        r=p2;
    }
    return 1;
}
int bingji(LinkList &S1,LinkList &S2){
    LNode *p1,*p2;
    p1=S1->next,p2=S2->next;
    LNode *S3,*p3;
    S3=S1;
    p3=S3;
    while(p1&&p2){
        if(p1->data<p2->data &&p1->data!=p3->data){
            p3->next=p1;
            p3=p1;
            p1=p1->next;
        }else if(p1->data>p2->data&&p2->data!=p3->data){
            p3->next=p2;
            p3=p2;
            p2=p2->next;
        }else if(p1->data==p2->data&&p1->data!=p3->data){
            p3->next=p1;
            p3=p1;
            p1=p1->next;
            p2=p2->next;
        }else if(p1->data==p3->data) p1=p1->next;
        else if(p2->data==p3->data) p2=p2->next;
    }
    while(p1){
        if(p3->data!=p1->data){
            p3->next=p1;
            p3=p1;
        }
        p1=p1->next;
    }
    while(p2){
        if(p3->data!=p2->data){
            p3->next=p2;
            p3=p2;
        }
        p2=p2->next;
    }//不能简单地使用三目运算符，因为必须考虑值相等的情况
    p3->next=NULL;//如果没有这一条，会报错一个测试点
    free(S2);//释放头结点
    p3=S3->next;
    if(p3==NULL){
        cout<<"NULL";
        return 0;
    }
    while(p3->next){
        cout<<p3->data<<" ";
        p3=p3->next;
    }cout<<p3->data;
    

    return 1;

}
int main(){
    LNode *S1,*S2;
    S1=new LNode,S2=new LNode;
    S1->next=NULL,S2->next=NULL;
    creatlist(S1,S2);
    bingji(S1,S2);
    return 0;
}
测试点 提示 内存(KB) 用时(ms) 结果 得分
0 样例 316 2 答案正确 5 / 5
1 一个是空表，另一个只有两个相同元素 316 2 答案正确 5 / 5
2 两个表都只有一个元素且相同 316 2 答案正确 5 / 5
3 两个表有很多相同元素 452 2 答案正确 5 / 5