A1161 Merging Linked Lists (25 分)

A1161 Merging Linked Lists (25 分)

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、L2，其中一个链表的长度 >= 另一个链表长度的两倍（没有具体说对应哪一个链表，需要自己确定）

短链表翻转合并到长链表，例如：

• 1->2->3->4->5
• 6->7
• 1->2->7->3->4->6->5

提示：测试样例保证没有空链表，并且保证长链表的长度至少是短链表长度的两倍

思路

1. 根据输入链表信息，建立结点值 到 结点的哈希映射表；
2. 把两个链表对应的结点直播分别装入vector<int> 中
3. 确认长链表与短链表
4. 根据规则合并两个链表
5. 最后输出结果

建议4、5步分开做，思路清晰一些；边合并链表边输出，容易出现小错误

AC代码

#include <bits/stdc++.h>
using namespace std;

struct node {
    int data, address, next;
};
unordered_map<int, node> arr;

int main() {
    int a1, a2, n;
    scanf("%d%d%d", &a1, &a2, &n);
    int address, data, next;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d%d", &address, &data, &next);
        arr[address] = {data, address, next};
    }
    vector<int> l1, l2;
    address = a1;
    while (address != -1) {
        l1.emplace_back(address);
        address = arr[address].next;
    }
    address = a2;
    while (address != -1) {
        l2.emplace_back(address);
        address = arr[address].next;
    }
    int len1 = l1.size(), len2 = l2.size();
    // assuming l1 is the longer list, l2 is the shorter one;
    if (len1 < len2) {
        swap(len1, len2);
        swap(l1, l2);
    }
    vector<int> res;
    for (int i = 0; i < l1.size(); ++i) {
        res.emplace_back(l1[i]);
        if (i & 1 && !l2.empty()) {
            res.emplace_back(l2.back());
            l2.pop_back();
        }
    }
    int len = len1 + len2; // res.size();
    for (int i = 0; i < len; ++i) {
        printf("%05d %d ", arr[res[i]].address, arr[res[i]].data);
        if (i == len - 1) printf("-1\n");
        else printf("%05d\n", arr[res[i + 1]].address);
    }
    return 0;
}