4273.链表合并

caution

原题链接：https://www.acwing.com/problem/content/4276/

思路

因为单从输入无法判断两条链分别怎么存储，所以先将输入存到一个链表中，再根据头节点分别遍历两条链表后存储到两个数组中。最后模拟反转和插入操作即可。

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

typedef pair<int, int> PII;

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

int main() {
    cin >> h1 >> h2 >> n;

    for (int i = 0; i < n; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        e[a] = b;
        ne[a] = t;
    }
    vector<PII> a, b, c;
    // 存链表 l1 的地址和值
    for (int i = h1; i != -1; i = ne[i])
        a.push_back({i, e[i]});
    // 存链表 l2 的地址和值
    for (int i = h2; i != -1; i = ne[i])
        b.push_back({i, e[i]});

    // 判断长度选出较短的链表，这里默认认为 a 是长的，b 是短的
    if (a.size() < b.size())
        swap(a, b);
    // 直接合并链表，存储到 c 中
    for (int i = 0, j = b.size() - 1; i < a.size(); i += 2, j--) {
        c.push_back(a[i]);
        if (i + 1 < a.size())
            c.push_back(a[i + 1]);
        if (j >= 0)
            c.push_back(b[j]);
    }
    // 输出结果
    for (int i = 0; i < c.size(); i++) {
        printf("%05d %d ", c[i].first, c[i].second);
        if (i + 1 < c.size())
            printf("%05d\n", c[i + 1].first);
        else
            puts("-1");
    }

    return 0;
}