链表合并
题目描述
给定两个单链表 $L_1 = a_1 → a_2 → \cdot \cdot \cdot → a_{n − 1} → a_n$ 和 $L_2 = b_1 → b_2 → \cdot \cdot \cdot → b_{m − 1} → b_m$。
如果 $n \ge 2m$,你的任务是将较短的那个链表逆序,然后将之并入较长的链表,得到形如 $a_1 → a_2 → b_m → a_3 → a_4 → b_{m − 1} \cdot \cdot \cdot$ 的结果。
例如给定两个链表分别为 $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 \le N \le 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
正解:链表
典型的双链表问题。
这里用数组模拟链表。
思路其实很简单,但实现稍有些困难。我们开一个 $Next$ 数组来存当前节点的下一个节点,$Prev$ 数组来存当前节点的上一个节点。然后比较 $L_1$,$L_2$ 的长度,如果 $Length_{L_1} \gt Length_{L_2}$,就交换两个链表。最后输出两个 $L_2$ 的节点(正序),输出一个 $L_1$ 的节点(倒序),输出两个 $L_2$ 的节点(正序),输出一个 $L_1$ 的节点(倒序),……,直到 $L_1$ 的节点都被输出,再依次输出 $L_2$ 剩下的节点即可。
AC Code
#include <iostream>
#include <cstdio>
#include <cstring>
#define k 5
#define N 100005
using namespace std;
int n, x, y, z, h1, h2, len1, len2, t1, t2, dat[N], nxt[N], prv[N];
pair <int, int> count (int head)
{
int res1 = 1, res2;
for (res2 = head; ~nxt[res2]; res2 = nxt[res2], res1 ++);
return make_pair (res1, res2);
}
int main ()
{
cin >> h1 >> h2 >> n, memset (nxt, -1, sizeof (nxt)), memset (prv, -1, sizeof (prv));
while (n --)
{
cin >> x >> y >> z, dat[x] = y;
if (~x)
{
nxt[x] = z;
}
if (~z)
{
prv[z] = x;
}
}
len1 = count (h1).first, t1 = count (h1).second, len2 = count (h2).first, t2 = count (h2).second;
if (len1 > len2)
{
swap (h1, h2), swap (len1, len2), swap (t1, t2);
}
for (int i = 1; i <= len1; i ++)
{
printf ("%05d %d ", h2, dat[h2]), h2 = nxt[h2], printf ("%05d\n", h2);
printf ("%05d %d ", h2, dat[h2]), h2 = nxt[h2], printf ("%05d\n", t1);
printf ("%05d %d ", t1, dat[t1]), t1 = prv[t1];
if (~h2)
{
printf ("%05d\n", h2);
}
else
{
puts ("-1");
}
}
for (int i = (len1 << 1) + 1; i < len2; i ++)
{
printf ("%05d %d ", h2, dat[h2]), h2 = nxt[h2], printf ("%05d\n", h2);
}
if (len1 << 1 < len2)
{
printf ("%05d %d -1", h2, dat[h2]);
}
return 0;
}