<---
大佬们点个赞吧qwq
$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $
给定两个单链表 $L_1=a_1→a_2→…→a_{n−1}→a_n$ 和 $L_2=b_1→b_2→…→b_{m−1}→b_m$,满足:$n≥2m$。
你的任务是将较短的那个链表逆序,然后将之并入较长的链表,得到形如 $a_1→a_2→b_m→a_3→a_4→b_{m−1}…$ 的结果。
例如给定两个链表分别为 $6→7$ 和 $1→2→3→4→5$,你应该输出 $1→2→7→3→4→6→5$。
补充
本题中可能包含不在两个单链表中的节点,这些节点无需考虑。
输入格式
输入首先在第一行中给出两个链表 $L_1$ 和 $L_2$ 的头结点的地址,以及正整数 $N$,即给定的结点总数。
一个结点的地址是一个 $5$ 位数的非负整数(可能包含前导 $0$),空地址NULL
用 $−1$ 表示。
随后 $N$ 行,每行按以下格式给出一个结点的信息:
Address Data Next
其中 Address
是结点的地址,Data
是不超过 $10^5$ 的正整数,Next
是下一个结点的地址。
题目保证没有空链表,并且较长的链表至少是较短链表的两倍长。
输出格式
按顺序输出结果链表,每个结点占一行,格式与输入相同。
数据范围
$1≤N≤10^5$
输入样例:
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
输出样例:
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1
思路
这道题竟然没有算法标签真奇怪
看这题的意思应该是数组模拟链表或者写结构体喽!因为懒得写结构体要节省码长就来说说数组模拟链表吧!
1. 读入头节点和节点数
2. 读入其他节点
3. 从头节点开始一步一步往下走,构成链表(这一步就可以筛掉不在两个单链表中的节点)
4. 按题意模拟,将较短的那个链表逆序,然后和较长的一起插到答案链表里面
5. 输出答案
坑点
这道题的坑点主要在这几点:
1. 读入(边界问题)
2. 模拟(容易忘了逆序,$n≥2m$)
3. 输出(地址要用 $5$ 位)
代码
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int d[N], ne[N], a1, b1; // d: 结点的值, ne: 下一个节点的地址
int a[N], b[N], res[N], len_a, len_b, len_res; // a: L₁, b: L₂, res: 答案
int main()
{
cin >> a1 >> b1 >> n; // 读入
a[0] = a1, b[0] = b1;
while (n -- )
{
int addr;
cin >> addr >> d[addr] >> ne[addr];
}
int i = a1; // 初始化a(这个地方要小心)
do
{
a[len_a ++ ] = i;
i = ne[i]; // i往后移一个节点
}
while (~i); // 如果结点的地址是NULL就结束
i = b1; // 初始化b
do // 同理
{
b[len_b ++ ] = i;
i = ne[i];
}
while (~i);
int l = len_a + len_b, idx = 0; // l: 要插的节点数, idx: 较长的链表插到哪了
for (i = 0; i < l && len_b && len_a; i ++ ) // 普通插入(插两个较长链表里的节点,再插一个较短链表里的节点)
{
if (i % 3 == 2) res[len_res ++ ] = (len_a > len_b ? b[ -- len_b] : a[ -- len_a]); // 插短的
else res[len_res ++ ] = (len_a > len_b ? a[idx ++ ] : b[idx ++ ]); // 插长的
}
while (idx < len_a) res[len_res ++ ] = a[idx ++ ]; // 把较长的链表剩下的元素插完
while (idx < len_b) res[len_res ++ ] = b[idx ++ ];
for (i = 0; i < len_res; i ++ ) // 输出答案
{
printf("%05d %d ", res[i], d[res[i]]); // printf节省码长
if (i == len_res - 1) puts("-1"); // 最后一个就输出NULL
else printf("%05d\n", res[i + 1]); // 否则输出下一个的地址(注意换行)
}
return 0; // 结束
}
Orz
为什么有人给我点倒赞
致歉:因为今天要上学,我只能下午再发题解了,请见谅