1161 Merging Linked Lists – PAT甲级真题

Given two singly linked lists L1=a1→a2→⋯→an−1→an and L2=b1→b2→⋯→bm−1→bm. If n≥2m, you are supposed to reverse and merge the shorter one into the longer one to obtain a list like a1→a2→bm→a3→a4→bm−1⋯. For example, given one list being 6→7 and the other one 1→2→3→4→5, you must output 1→2→7→3→4→6→5.

Input Specification:

Each input file contains one test case. For each case, the first line contains the two addresses of the first nodes of L1 and L2, plus a positive N (≤105) which is the total number of nodes given. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is a positive integer no more than 105, and Next is the position of the next node. It is guaranteed that no list is empty, and the longer list is at least twice as long as the shorter one.

Output Specification:

For each case, output in order the resulting linked list. Each node occupies a line, and is printed in the same format as in the input.

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

题目大意：给定两个单链表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，一个结点的地址是一个5位数的非负整数，空地址 NULL用-1表示。随后N行，每行按以下格式给出一个结点的信息：Address Data Next，其中Address是结点的地址，Data是不超过10的5次方的正整数，Next是下一个结点的地址，题目保证没有空链表，并且较长的链表至少是较短链表的两倍长。按顺序输出结果列表，每个结点占一行，格式与输入相同。
分析：用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题解离线版