秋招每日一题T6——链表合并

题目描述

给定两个单链表 L1=a1→a2→…→an−1→an 和 L2=b1→b2→…→bm−1→bm。

如果 n≥2m，你的任务是将较短的那个链表逆序，然后将之并入较长的链表，得到形如 a1→a2→bm→a3→a4→bm−1… 的结果。

例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。

补充
本题中可能包含不在两个单链表中的节点，这些节点无需考虑。

输入格式
输入首先在第一行中给出两个链表 L1 和 L2 的头结点的地址，以及正整数 N，即给定的结点总数。

一个结点的地址是一个 5 位数的非负整数（可能包含前导 0），空地址 NULL 用 −1 表示。

随后 N 行，每行按以下格式给出一个结点的信息：

Address Data Next
其中 Address 是结点的地址，Data 是不超过 105 的正整数，Next 是下一个结点的地址。

题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。

输出格式
按顺序输出结果链表，每个结点占一行，格式与输入相同。

数据范围
1≤N≤10⁵’

思路

①上来以为是一道大模拟，但是在AcWing的题解中看到了一个非常marvelous的妙手，即使用vector来表示链表。最初存储时，使用类似于邻接表的方法，开一个e和ne数组来存储输入的数据。
②将链表a和b表示出来之后这就是一道水题了，开一个新的vector来表示答案，先存储两个a链表数据，再存一个b的数据（注意，b有可能比a的一半还短，需要判断一下b是否到头了，到头了后面全放a即可）。

代码

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5 + 5;
int e[maxn] = { 0 }, ne[maxn] = { 0 };
int f1, f2, n;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> f1 >> f2 >> n;
	for (int i = 1; i <= n; i++) {
		int address;
		cin >> address;
		cin >> e[address] >> ne[address];
	}
	vector<int> a, b;
	for (int i = f1; i != -1; i = ne[i])	a.push_back(i);
	for (int i = f2; i != -1; i = ne[i])	b.push_back(i);
	if (a.size() < b.size())	swap(a, b);
	reverse(b.begin(), b.end());

	vector<int> res;
	for (int i = 0,j = 0; i < a.size();) {
		res.push_back(a[i++]);
		if (i % 2 == 0 && j < b.size())	res.push_back(b[j++]);
	}
	for (int i = 0; i < res.size(); i++) {
		printf("%05d %d ", res[i], e[res[i]]);
		if (i == res.size() - 1)	printf("-1\n");
		else {
			printf("%05d\n", res[i+1]);
		}
	}
	return 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