1105 链表合并

Statement

Metadata

作者: 陈越
单位: 浙江大学
代码长度限制: 16 KB
时间限制: 400 ms
内存限制: 64 MB

给定两个单链表 $L_1 = a_1 \to a_2\to \cdots \to a_{n-1}\to a_n$ 和 $L_2 = b_1 \to b_2\to \cdots \to b_{m-1}\to b_m$ 。如果 $n\ge 2m$ ，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如 $a_1 to a_2 to b_{m} to a_3 to a_4 to b_{m-1}cdots $ 的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。

输入格式

输入首先在第一行中给出两个链表 $L_1$ 和 $L_2$ 的头结点的地址，以及正整数 $N$ ( $\le 10^5$ )，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。

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

Address Data Next

其中 Address 是结点的地址，Data 是不超过 $10^5$ 的正整数，Next 是下一个结点的地址。题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。

输出格式

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

输入样例

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

Last update: May 4, 2022