链表合并（暑假每日一题 3）

给定两个单链表 $L_1=a_1\to a_2\to \dots \to a_{n-1}\to a_n$ 和
$L_2=b_1\to b_2\to \dots \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}\dots$ 的结果。

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

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

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

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

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

Address Data Next
1

其中 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
1
2
3
4
5
6
7
8

输出样例：

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
6
7

---

#include
#include
#include

using namespace std;

const int N = 1000010;

int n, h1, h2;
int e[N], ne[N];

int main(){
    
    cin >> h1 >> h2 >> n;
    
    int address, data, neaddress;
    for(int i = 0; i < n; i++){
        cin >> address >> data >> neaddress;
        e[address] = data;
        ne[address] = neaddress;
    }
    
    vector<int> v1, v2, v3;
    for(int i = h1; ~i; i = ne[i])
        v1.push_back(i);
    for(int i = h2; ~i; i = ne[i])
        v2.push_back(i);
    
    if(v1.size() < v2.size()) swap(v1, v2);
    
    reverse(v2.begin(), v2.end());
    for(int i = 0; i < v1.size(); i++){
        v3.push_back(v1[i]);
        if(i % 2 && i / 2 < v2.size()) v3.push_back(v2[i/2]);
    }
    
    for(int i = 0; i < v3.size(); i++){
        
        printf("%05d %d ", v3[i], e[v3[i]]);
        if(i == v3.size() - 1) puts("-1");
        else printf("%05d\n", v3[i+1]);
    }
    
}
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