7-52 两个有序链表序列的交集 (20 分)(思路加详解尾插法)come Boby!

输入格式:

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

输出格式:

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

输入样例:

1 2 5 -1

2 4 5 8 10 -1

输出样例:

2 5

[](()二：思路

===================================================================

1.首先是储存数据，我用的是尾插法

2.考虑如何找出交集，需要注意的是，题目说的是非降序为（即后一个一定比前一个值大），那么我们在处理交集合的时候，就可以用到了比较元素大小，直接让指针指向后一个，而不用担心前一个会被忽略，因为两个序列均为非降序

[](()三：上码

===================================================================

#include<bits/stdc++.h>

using namespace std;

typedef struct Node* Link;

typedef struct Node{

int data;

Link next;

}nnode;

//输入链表(尾插法)

Link createLink(){

Link head = (Link)malloc(sizeof(struct Node));

Link rear;

rear = head;

while(1){

int num;

cin >> num;

if(num == 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 -1)

break;

Link p = (Link)malloc(sizeof(struct Node));

p->data = num;

rear->next = p;

rear = p;

}

rear->next = NULL;

return head;

}

Link newLink(Link L1,Link L2){

Link l1 = L1->next;

Link l2 = L2->next;

//新建一个链表 存的元素为交集

Link head = (Link)malloc(sizeof(struct Node));

Link rear;

rear = head;

while(l1 && l2){

//题目给出的非降序（即后一个一定比前一个值大）

if(l1->data > l2->data){

l2 = l2->next;

}else if(l1->data < l2->data){

l1 = l1->next;

}else if(l1->data == l2->data){

Link p = (Link)malloc(sizeof(struct Node));

p->data = l1->data;

rear->next = p;

rear = p;

l1 = l1->next;

l2 = l2->next;

//return 0;

}

}

rear->next = NULL;

return head;

}

void printLink(Link L){

Link l = L->next;//头结点并未赋值，所以要用头结点的下一个结点

if(l == NULL){

cout << "NULL";

}

int flag = 0;

while(l){

if(flag == 0)

cout << l->data;

else

cout << ' ' << l->data;

flag = 1;

l = l->next;

}

}

int main(){

Link L1 = createLink();

Link L2 = createLink();

Link L3 = newLink(L1,L2);

printLink(L3);

}

[](()四：其他做法的失败码

=========================================================================

[](()1：用了 vector 容器（最后一个点超时）

#include<bits/stdc++.h>

using namespace std;

int main(){

vector<int>v1,v2,v3;

set<int>s[2];

set<int>::iterator st;

while(1){

int temp1;

cin >> temp1;

if(temp1 == -1)

break;

v1.push_back(temp1);

}

while(1){

int temp2;

cin >> temp2;

if(temp2 == -1)

break;

v2.push_back(temp2);

}

//判断相同的元素

int num1 = v1.size() > v2.size() ? v1.size() : v2.size();//求出较大的值

int num2 = v1.size() < v2.size() ? v1.size() : v2.size();//求出较小的值

for(int i = 0; i < num2; i++){

for( int j = 0; j < num1; j++){

if(v1[i] == v2[j]){

v3.push_back(v1[i]);

break;

}

}

}

if(v3.size() != 0){

for(int i = 0; i < v3.size(); i++){

if(i != v3.size() - 1){

cout << v3[i] << ' ';

}else{

cout << v3[i];

}

}

}else{

cout << "NULL";