PAT 链表反转 + 链表合并

满分

易错点: 只需要每隔两个加入一个数据即可,因为题目给出了,长的链表一定会是两倍多比短链表

但是题目并未仔细说明

/**
题意:两个链表合并

用一个并查集去存放,再用两个vector来存储,反转短的vector,再合并
map存储节点值

*/
#include <iostream>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
const int N = 100010;
int ne[N];
int main()
{
    int l1, l2, m;
    cin >> l1 >> l2 >> m;
    unordered_map<int,int> wgt;
    while (m --)
    {
        int a, b, w;
        scanf("%d %d %d", &a, &w, &b);
        wgt[a] = w;
        ne[a] = b;
    }
    vector<int> v1, v2;
    for(int i = l1; i != -1; i = ne[i]) v1.push_back(i);
    for(int i = l2; i != -1; i = ne[i]) v2.push_back(i);

    if (v2.size() > v1.size())
    {
        vector<int> tmp = v1;
        v1 = v2;
        v2 = tmp;
    }

    reverse(v2.begin(), v2.end());
    vector<int> res;
    for(int i = 0, idx = 0; i < v1.size();) // cnt总长度,idx是v2长度, i是v1长度
    {
        // 细节操作(这里循环越简单越不容易出错)
        res.push_back(v1[i++]);
        if (i % 2 == 0 && idx < v2.size()) res.push_back(v2[idx++]);

    }
    for(int i = 0; i < res.size(); i++)
    {
        printf("%05d %d ", res[i], wgt[res[i]]);
        if (i != res.size() - 1) printf("%05d\n", res[i + 1]);
        else printf("-1\n");
    }

}

22分代码, 一个测试点错误 不应该用k倍,只需要用2倍即可

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100010;
int e[N], p[N];

int main()
{
    int n1, n2, m;
    cin >> n1 >> n2 >> m;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> c >> b;
        p[a] = b;
        e[a] = c;
    }
    // 赋值两个链表
    vector<int> a, b, c;
    for(int i = n1; i != -1; i = p[i]) a.push_back(i);

    for(int i = n2; i != -1; i = p[i]) b.push_back(i);
    if (a.size() < b.size())
    {
        c = a;
        a = b;
        b = c;
        reverse(b.begin(), b.end());
        c.clear();
    }
    int k = a.size() / b.size();
    int max_size = a.size() + b.size();
    int x = 0, y = 0, cnt = 0;

    for(int i = 0; i < max_size; i++)
    {

        if (cnt == k)
        {
            cnt = 0;
            if (x < b.size()) c.push_back(b[x++]);
            continue; // continue 不写,会导致下面cnt++ ,少算节点

        }else{
            if (y < a.size()) c.push_back(a[y++]);
        }
        cnt++;
    }
    for(int i = 0; i < c.size(); i++)
    {
        printf("%05d %d ", c[i], e[c[i]]);
        if (i != c.size() - 1) printf("%05d\n", c[i + 1]);
        else printf("-1");
    }
}