1105 链表合并 – PAT乙级真题

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

分析：用vector<int> L1、L2存储题目中给定的两个链表，vector<int> ans保存合并后的链表。将较长的一个链表存储在L1中，如果原本L1较短，则将L1与L2用swap函数互相置换~在链表合并的过程中，i从0开始，将L1中每个结点添加到ans中，如果当前i是奇数（i & 1不等于0）就把L2的一个结点添加到ans中，直到L2中没有剩余元素~如此反复，就大功告成啦。

#include <iostream>
#include <vector>
using namespace std;
struct node {
    int data, next;
}A[100000];
vector<int> L1, L2, ans;
int sa, sb, n, a, ta, tb, c;
int main() {
    cin >> sa >> sb >> n;
    for (int i = 0; i < n; i++) {
        cin >> a >> A[a].data >> A[a].next;
    }
    ta = sa;
    while (ta != -1) {
        L1.push_back(ta);
        ta = A[ta].next;
    }
    tb = sb;
    while (tb != -1) {
        L2.push_back(tb);
        tb = A[tb].next;
    }
    if (L1.size() < L2.size()) swap(L1, L2);
    for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {
        ans.push_back(L1[i]);
        if (i & 1 && c >= 0) ans.push_back(L2[c--]);
    }
    for (int i = 1; i < ans.size(); i++) {
        printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);
    }
    printf("%05d %d -1", ans.back(), A[ans.back()].data);
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

struct node {

int data, next;

}A[100000];

vector<int> L1, L2, ans;

int sa, sb, n, a, ta, tb, c;

int main() {

cin >> sa >> sb >> n;

for (int i = 0; i < n; i++) {

cin >> a >> A[a].data >> A[a].next;

}

ta = sa;

while (ta != -1) {

L1.push_back(ta);

ta = A[ta].next;

}

tb = sb;

while (tb != -1) {

L2.push_back(tb);

tb = A[tb].next;

}

if (L1.size() < L2.size()) swap(L1, L2);

for (int i = 0, c = L2.size() - 1; i < L1.size(); i++) {

ans.push_back(L1[i]);

if (i & 1 && c >= 0) ans.push_back(L2[c--]);

}

for (int i = 1; i < ans.size(); i++) {

printf("%05d %d %05d\n", ans[i-1], A[ans[i-1]].data, ans[i]);

}

printf("%05d %d -1", ans.back(), A[ans.back()].data);

return 0;

}

❤ 点击这里 -> 订阅《PAT | 蓝桥 | LeetCode学习路径 & 刷题经验》by 柳婼

❤ 点击这里 -> 订阅《从放弃C语言到使用C++刷算法的简明教程》by 柳婼

❤ 点击这里 -> 订阅PAT甲级乙级、蓝桥杯、GPLT天梯赛、LeetCode题解离线版