PTA乙级 1105 链表合并——25分

给定两个单链表 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 (≤105)，即给定的结点总数。⼀个结点的地址是⼀个 5 位数的⾮负整数，空地址 NULL ⽤ -1 表示。
随后 N ⾏，每⾏按以下格式给出⼀个结点的信息：

Address Data Next
1

其中 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
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

|代码长度限制 | 时间限制 | 内存限制 |
| 16KB | 400ms | 64MB |

思路：
出现过好几次的题了,代码中会给出注释,不再赘述

代码：

#include 
using namespace std;
struct node {
    int adress, data, next;
} N[100005];
vector<node> v1, v2, v3;
int sa, sb, n, t;
int main() {
    cin >> sa >> sb >> n;
    for (int i = 0; i < n; i++) {
        cin >> t ;
        N[t].adress = t;
        cin >> N[t].data >> N[t].next;
    }
    while (sa != -1) {
        v1.emplace_back(N[sa]);
        sa = N[sa].next;
    }
    while (sb != -1) {
        v2.emplace_back(N[sb]);
        sb = N[sb].next;
    }
    if (v1.size() < v2.size()) swap(v1, v2); //始终保持v1为较长的那个链表,v2为较短的那个
    for (int i = 0, j = v2.size() - 1; i < int(v1.size()); i++) {
        v3.push_back(v1[i]);
        if (i % 2 != 0 && j >= 0) v3.push_back(v2[j--]); //下标为奇数个的时候插入较短链表的元素
    }
    int len = int(v3.size());
    for (int i = 0; i < len; i++) {
        if (i != len - 1) v3[i].next = v3[i + 1].adress; //重新安排地址，使前后节点的next和adress相关联，注意最后以-1结束
        else v3[i].next = -1;
    }
    for (int i = 0; i < len; i++) {
        if (i != len - 1) printf("%05d %d %05d\n", v3[i].adress, v3[i].data, v3[i].next); //输出部分用scanf和%05d控制格式
        else printf("%05d %d -1", v3[i].adress, v3[i].data);
    }
    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