当前位置：首页 > article >正文

PTA 1105-链表合并（C++）

article 2025/3/31 16:43:53

给定两个单链表𝐿1=𝑎1→𝑎2→⋯→𝑎𝑛−1→𝑎𝑛L1=a1→a2→⋯→an−1→an和𝐿2=𝑏1→𝑏2→⋯→𝑏𝑚−1→𝑏𝑚L2=b1→b2→⋯→bm−1→bm 。如果𝑛≥2𝑚n≥2m，你的任务是将比较短的那个链表逆序，然后将之并入比较长的那个链表，得到一个形如𝑎1→𝑎2→𝑏𝑚→𝑎3→𝑎4→𝑏𝑚−1⋯a1→a2→bm→a3→a4→bm−1⋯的结果。例如给定两个链表分别为 6→7 和 1→2→3→4→5，你应该输出 1→2→7→3→4→6→5。

输入格式：

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

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

Address Data Next

Copy

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

Copy

输出样例：

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

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

struct node {
    int addr;
    int data;
    int next;
};
map<int, node> mp;
vector<node> list;
vector<node> list2;
int main() {
    int l1, l2;
    int n;
    cin >> l1 >> l2 >> n;
    for (int i = 0; i < n; ++i) {
        node t;
        cin >> t.addr >> t.data >> t.next;
        mp[t.addr] = t; //存入map
    }
    for (int p = l1; p != -1; p = mp[p].next) {//存入vector容器
        list.push_back(mp[p]);
    }
    for (int p = l2; p != -1; p = mp[p].next) {
        list2.push_back(mp[p]);
    }

    if (list.size() < list2.size()) {
        if (list2.size() >= 2 * list.size()) { //判断是否大于2m
            reverse(list.begin(), list.end());
        } else {
            return 0;
        }
    } else {
        if (list.size() >= 2 * list2.size()) {
            reverse(list2.begin(), list2.end());
            swap(list, list2);
        } else {
            return 0;
        }
    }

    vector<node> m;//建立vector m,将新链表加入m,便于后面输出
    int index1 = 0, index2 = 0;
    while (index1 < list2.size() || index2 < list.size()) {
        if (index1 < list2.size()) {
            m.push_back(list2[index1++]);
        }
        if (index1 < list2.size()) {
            m.push_back(list2[index1++]);
        }
        if (index2 < list.size()) {
            m.push_back(list[index2++]);
        }
    }
    for (int i = 0; i < m.size() - 1; ++i) {
        m[i].next = m[i + 1].addr;
    }
    m.back().next = -1;//将最后一个的next改为-1
    for (int i = 0; i < m.size(); ++i) {
        if (i < m.size() - 1) {
            printf("%05d %d %05d\n", m[i].addr, m[i].data, m[i].next);
        } else {
            printf("%05d %d -1\n", m[i].addr, m[i].data);
        }
  
    }

    return 0;
}