PAT B1105 链表合并

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
using namespace std;
struct Node {
    string address;
    int data;
    string next;
};
int main() {
    string address1, address2;
    string address, next;
    int n, data;
    map<string, Node> list;
    vector<Node> list1, list2, listans;
    cin >> address1 >> address2 >> n;
    while (n--) {
        cin >> address >> data >> next;
        Node node;
        node.address = address;
        node.data = data;
        node.next = next;
        list[address] = node;
    }

    while (1) {
        if (address1 == "-1") break;
        list1.push_back(list[address1]);
        address1 = list[address1].next;
    }
    while (1) {
        if (address2 == "-1") break;
        list2.push_back(list[address2]);
        address2 = list[address2].next;
    }
    if (list2.size() < list1.size()) {
        reverse(list2.begin(), list2.end());
    }
    else {
        reverse(list1.begin(), list1.end());
    }
    int index1, index2;
    for (index1 = 0, index2 = 0; index1<list1.size() && index2 < list2.size();) {
        if (list1.size() > list2.size()) {
            listans.push_back(list1[index1++]);
            listans.push_back(list1[index1++]);
            listans.push_back(list2[index2++]);
        }
        else {
            listans.push_back(list2[index2++]);
            listans.push_back(list2[index2++]);
            listans.push_back(list1[index1++]);
        }
    }
    for (; index1 < list1.size();) {
        listans.push_back(list1[index1++]);
    }
    for (; index2 < list2.size();) {
        listans.push_back(list2[index2++]);
    }

    for (int i = 0; i < (listans.size() - 1); i++) {
        cout << listans[i].address << " " << listans[i].data << " " << listans[i + 1].address << endl;
    }
    cout << listans[listans.size() - 1].address << " " << listans[listans.size() - 1].data << " -1" << endl;
    return 0;
}