给定两个单链表𝐿1=𝑎1→𝑎2→⋯→𝑎𝑛−1→𝑎𝑛L1=a1→a2→⋯→an−1→an和𝐿2=𝑏1→𝑏2→⋯→𝑏𝑚−1→𝑏𝑚L2=b1→b2→⋯→bm−1→bm 。如果𝑛≥2𝑚n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如𝑎1→𝑎2→𝑏𝑚→𝑎3→𝑎4→𝑏𝑚−1⋯a1→a2→bm→a3→a4→bm−1⋯的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。
输入格式：
输入首先在第一行中给出两个链表𝐿1L1和𝐿2L2的头结点的地址，以及正整数𝑁(≤105)N(≤105)，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。
随后 行，每行按以下格式给出一个结点的信息：
Address Data Next
Copy
其中 Address 是结点的地址，Data 是不超过105105的正整数，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
Copy
输出样例：
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;struct node {int addr;int data;int next;
};
map<int, node> mp;
vector<node> list;
vector<node> list2;
int main() {int l1, l2;int n;cin >> l1 >> l2 >> n;for (int i = 0; i < n; ++i) {node t;cin >> t.addr >> t.data >> t.next;mp[t.addr] = t; //存入map}for (int p = l1; p != -1; p = mp[p].next) {//存入vector容器list.push_back(mp[p]);}for (int p = l2; p != -1; p = mp[p].next) {list2.push_back(mp[p]);}if (list.size() < list2.size()) {if (list2.size() >= 2 * list.size()) { //判断是否大于2mreverse(list.begin(), list.end());} else {return 0;}} else {if (list.size() >= 2 * list2.size()) {reverse(list2.begin(), list2.end());swap(list, list2);} else {return 0;}}vector<node> m;//建立vector m,将新链表加入m,便于后面输出int index1 = 0, index2 = 0;while (index1 < list2.size() || index2 < list.size()) {if (index1 < list2.size()) {m.push_back(list2[index1++]);}if (index1 < list2.size()) {m.push_back(list2[index1++]);}if (index2 < list.size()) {m.push_back(list[index2++]);}}for (int i = 0; i < m.size() - 1; ++i) {m[i].next = m[i + 1].addr;}m.back().next = -1;//将最后一个的next改为-1for (int i = 0; i < m.size(); ++i) {if (i < m.size() - 1) {printf("%05d %d %05d\n", m[i].addr, m[i].data, m[i].next);} else {printf("%05d %d -1\n", m[i].addr, m[i].data);}}return 0;
} 
