题目描述

给定两个单链表 L1=a1→a2→…→an−1→an 和 L2=b1→b2→…→bm−1→bm，满足：n≥2m。

你的任务是将较短的那个链表逆序，然后将之并入较长的链表，得到形如 a1→a2→bm→a3→a4→bm−1… 的结果。

例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。

样例

00100 01000 7
02233 2 34891
00100 6 00001
34891 3 10086
01000 1 02233
00033 5 -1
10086 4 00033
00001 7 -1

01000 1 02233
02233 2 00001
00001 7 34891
34891 3 10086
10086 4 00100
00100 6 00033
00033 5 -1

根据题目意思做。
这里使用结构体存下当前结点的data以及下一个结点ne,用一个unordered_map映射当前的地址，这里地址可以使用int存储，后面输出的时候只需要补0就可。
这里将数据连起来的方式就是数组模拟链表，算法基础课模板中有详细的写法。

我在做的时候，觉得麻烦的地方，一个是找短链表，一个是短链表逆序，还有就是最后的输出。
找短链表的时候，看到题目是说保证长链表至少是短链表的两倍，就先遍历一遍一号链表，用cnt记录长度，如果2 * cnt >= n(总长)，就说明是一号是长链表，反之就说明是短链表。
反转链表 这里写了个re_verse()函数，里面两个参数，一个是当前地址，还有一个是当前地址的上一个地址，因为逆序后
地址的顺序也需要调整，所以传递两个参数，另外，在这里是重新再写了一个链表来存储逆序链表。
最后输出，我是从1开始循环，因此就是每当是3的倍数的时候就是短链表，具体判断时候就是，先判断i % 3 == 0,如果成立 就打印当前地址，以及对应的data。打印下一个地址的时候，是额外判断(i + 1) % 3 ==0是否成立，也就是判断结点是3的倍数的上一个结点。

具体代码如下，这里一开始先用的cin, cout，但超时了，后来才改成printf，yysy printf确实香。。。

C++ 代码

#include <iostream>
#include <string>
#include <unordered_map>
#include <cstdio>

using namespace std;
const int N = 100010;
int h1, h2, rh;
unordered_map<int, int> u1, u2;
int n, m;
struct node{
    int data;
    int ne;
    node(int data, int ne){
        this->data = data;
        this->ne = ne;
    }
    node() {}
}nd[N], rnd[N / 2];

void re_verse(int h, int pre){
    if(nd[u1[h]].ne != -1){
        re_verse(nd[u1[h]].ne, h);
    }
    if(m == 0)  rh = h;
    u2[h] = ++ m;
    rnd[m] = {nd[u1[h]].data, pre};
}

int main(){
    // ios::sync_with_stdio(false);
    // cin.tie(0);

    // cin >> h1 >> h2 >> n;
    scanf("%d%d%d", &h1, &h2, &n);

    for(int i = 1; i <= n; i ++){
        int add, ne;
        int data;
        scanf("%d%d%d", &add, &data, &ne);
        //cin >> add >> data >> ne;
        u1[add] = ++ m;
        nd[m] = {data, ne};
    }
    int cnt = 0;
    int t = h1;

    while(nd[u1[t]].ne != -1){
        t = nd[u1[t]].ne;
        cnt ++;
    }
    m = 0;
    if(n >= 2 * cnt){
        t = h2;
        re_verse(h1, -1);
        int t2 = rh; // 逆链表的头节点，也就是原来顺序链表的尾结点
        for(int i = 1; i <= n; i ++){
            if(i % 3 == 0 && t2 != -1){
                printf("%05d %d ", t2, rnd[u2[t2]].data);
                t2 = rnd[u2[t2]].ne;
            }
            else if(t != -1){
                 printf("%05d %d ", t, nd[u1[t]].data);
                // cout << nd[u1[t]].ne << endl;
                t = nd[u1[t]].ne;
            }
            if((i + 1) % 3 == 0 && t2 != -1){
                printf("%05d\n", t2);
            }
            else if(t != -1)    printf("%05d\n", t);

        }
    }
    else{
        t = h1;
        re_verse(h2, -1);
        int t2 = rh;
        for(int i = 1; i <= n; i ++){
            if(i % 3 == 0 && t2 != -1){
                printf("%05d %d ", t2, rnd[u2[t2]].data);
                //cout << t2 << " " << rnd[u2[t2]].data << " ";
                t2 = rnd[u2[t2]].ne;
            }
            else if(t != -1){
                printf("%05d %d ", t, nd[u1[t]].data);
                //cout << t <<  " " << nd[u1[t]].data << " ";
                // cout << nd[u1[t]].ne << endl;
                t = nd[u1[t]].ne;
            }
            if((i + 1) % 3 == 0 && t2 != -1){
                printf("%05d\n", t2);
                //cout << t2 << endl;
            }
            else if(t != -1)    printf("%05d\n", t);

        }
    }
    printf("%d", -1); //这里把-1放在最后输出，放在上面循环里会出现问题。
    return 0;
}