7-52 两个有序链表序列的交集
https://pintia.cn/problem-sets/15/problems/2999
这道题思路很简单，从一个链表（循环的内层）中多次搜索另一个链表（循环的外层）里面的数字。不过经过了简单的优化：因为链表有序，因此每次找到后记录内层被查找链表的位置，这样可以不用每次都从头开始搜索。
优化前大规模数据大概是400ms，优化后300+ms。
但是一直找不到大规模数据这组样例哪里错了……以后有时间了再找下。
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
91
92
93
94
95
96
97
| #include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
typedef long long unsigned int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType data;
PtrToNode next;
};
typedef PtrToNode List;
inline List read(void) {
long long unsigned int X;
List L = NULL, now = L;
while ((cin >> X) && X != -1) {
List tmp = (List)malloc(sizeof(struct Node));
tmp->data = X;
tmp->next = NULL;
if (now == NULL) {
L = tmp;
now = tmp;
}
else {
now->next = tmp;
now = tmp;
}
}
return L;
}
inline void print(List L) {
if (L == NULL) {
cout << "NULL" << endl;
return;
}
while (L->next) {
cout << L->data<< " " ;
L = L->next;
}
cout << L->data << endl;
return;
}
List intersectionList(List L1,List L2) {
List inter = NULL, internow = NULL;
List L2begin = L2;
for (auto now1 = L1; now1; now1 =now1->next )
{
long long unsigned int data1 = now1->data;
for (auto now2 = L2begin; now2 && now2->data <= data1; now2 = now2->next)
{
long long unsigned int data2 = now2->data;
if (data1 == data2)
{
if (inter== NULL)
{
inter = (List)malloc(sizeof(struct Node));
inter->data = data1;
inter->next = NULL;
internow = inter;
}
else
{
List tmp = (List)malloc(sizeof(struct Node));;
tmp->data = data1;
tmp->next = NULL;
internow->next = tmp;
internow = internow->next;
}
L2begin = now2;
break;
}
}
}
return inter;
}
int main()
{
List L1 = read();
List L2 = read();
List inter = intersectionList(L1,L2);
print(inter);
return 0;
}
|