链表合并 分数 25

给定两个单链表 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。

输入格式：

输入首先在第一行中给出两个链表 L1​ 和 L2​ 的头结点的地址，以及正整数
N (≤105)，即给定的结点总数。一个结点的地址是一个 5 位数的非负整数，空地址 NULL 用 -1 表示。

随后 N 行，每行按以下格式给出一个结点的信息：

Address Data Next

其中 Address 是结点的地址，Data 是不超过 105 的正整数，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

输出样例：

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

思路：

将这两个链表用一个结构体保存表示

按链表的方式遍历这个结构体，用两个数组把两个链表按顺序取出来

小的逆序

然后按照两个大的一个小的输出，小的不够就输出大的，题目保证了大的一定够

输出方式：除第一个节点外，每个人先输出自己的地址和换行

                  所有节点输出自己的地址和自己的值 

                  最后输出-1

代码：

#include 
using namespace std;
const int N = 100010;
struct Node
{
    int num, next;
} node[N];
typedef pair<int, int> PII;
 
PII res1[N],res2[N];
 
void fun(PII res1[], PII res2[], int n1, int n2) {
    int p = 0, q = 0;
    for (int i = 1; i <= n1 + n2; i++) {
        if (i % 3 == 0) {
            if (q < n2) {
                if (i != 1)printf("%05d\n", res2[q].first);
                printf("%05d %d ", res2[q].first, res2[q].second);
                q++;
            }
            else {
                if (i != 1)printf("%05d\n", res1[p].first);
                printf("%05d %d ", res1[p].first, res1[p].second);
                p++;
            }
        }
        else {
            if (i != 1)printf("%05d\n", res1[p].first);
            printf("%05d %d ", res1[p].first, res1[p].second);
            p++;
        }
    }cout << "-1";
}
 
int main()
{
    int root1, root2, n;
    cin >> root1 >> root2 >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        cin >> node[a].num >> node[a].next;
    }
    int n1 = 0, n2 = 0;
    for (int i = root1; i != -1; i = node[i].next , n1++ ) {
        res1[n1] = { i,node[i].num };
    }
    for (int i = root2; i != -1; i = node[i].next, n2++) {
        res2[n2] = { i,node[i].num };
    }
    if (n1 > n2) {
        reverse(res2, res2 + n2);
        fun(res1, res2, n1, n2);
    }
    else {
        reverse(res1, res1 + n1);
        fun(res2, res1, n2, n1);
    }
 
    return 0;
}