1: subject

Given two single chain tables L1=a1→a2→…→an−1→an and L2=b1→b2→…→bm−1→bm.

If n≥2m, Your task is to reverse the shorter list , Then merge it into a longer linked list , Get the shape of a1→a2→bm→a3→a4→bm−1… Result .

For example, give two linked lists as 6→7 and 1→2→3→4→5, You should output 1→2→7→3→4→6→5.

Add
This question may contain nodes that are not in the two single linked lists , These nodes need not be considered .

Input format
Input first gives two linked lists in the first row L1 and L2 The address of the header node of , And positive integers N, That is, the total number of nodes given .

The address of a node is 5 Nonnegative integer of digits （ May contain leading 0）, Empty address NULL use −1 Express .

And then N That's ok , Each line gives the information of a node in the following format ：

Address Data Next
among Address Is the address of the node ,Data No more than 105 The positive integer ,Next Is the address of the next node .

The title ensures that there is no empty linked list , And the longer list is at least twice as long as the shorter list .

Output format
Output the result linked list in order , Each node occupies a row , The format is the same as the input .

Data range
1≤N≤105
sample input ：
00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1
sample output ：
01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1
difficulty ： Simple
when / Empty limit ：0.4s / 64MB
Total number of passes ：1673
Total attempts ：4062
source ：PAT Class a real topic 1161
Algorithm tags

2： Realization ：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;

const int N = 100010;

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

int main()
{
    
    scanf("%d%d%d", &h1, &h2, &n);
    while (n -- )
    {
    
        int addr, val, next;
        scanf("%d%d%d", &addr, &val, &next);
        v[addr] = val, ne[addr] = next;
    }

    vector<PII> a, b;
    for (int i = h1; i != -1; i = ne[i]) a.push_back({
    i, v[i]});
    for (int i = h2; i != -1; i = ne[i]) b.push_back({
    i, v[i]});

    if (a.size() < b.size()) swap(a, b);

    vector<PII> 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].x, c[i].y);
        if (i + 1 < c.size()) printf("%05d\n", c[i + 1].x);
        else puts("-1");
    }

    return 0;
}