1071: 绝世好题（19年期末机考T1）

题目描述

想必各位身经百战的同学都已经熟练掌握了如何写一个链表，数组的使用更是不在话下。下面我们就来写一个以链表为元素的数组吧！

你需要完成一个链表数组类型 LinkListArray，里面包含 $len$ 个保存正整数的单链表（你可以自由决定是否带头结点），并要求在任意时刻每个链表里的元素都是满足非严格升序排列的（可以有存在相同的元素），也就是说，在任意时刻，每个单链表中的第 0 个元素应该是这个单链表中非严格最小的元素，第 1 个元素应该是这个单链表中非严格次小的元素……链表中允许元素重复。开始时，每一个单链表中都没有元素。你应该支持以下操作（所有数均为0-base）：

0 在第 $s_1$ 个链表中加入数字 $s_2$
1 查询第 $s_1$ 个链表中的第 $s_2$ 个元素，如果第 $s_1$ 个链表中的元素数小于 $s_2$，则返回 -1。
2 将第 $s_1$ 个链表与第 $s_2$ 个链表合并成一个升序链表，保存为第 $s_1$ 个链表，将第 $s_2$ 个链表清空 ($s_1 \neq s_2$)。

对于如何合并两个有序链表得到一个新的有序链表，你应该使用如下算法：

1、如果两个链表都为空，则算法结束。

2、如果一个链表非空，另外一个链表为空，则将非空链表的最小元素从链表中取出，加入新链表的末尾。回到第1步。

3、如果两个链表皆非空，比较两个链表各自的最小元素，将两个元素较小的那个取出，加入新链表的末尾。回到第1步。

这样就得到了新的有序链表。当然，你应该自己填补算法的细节。

然而善良的助教已经写好了完整的 LinkListArray类，你只需要填补它所依赖的 LinkList 类就好啦！

注意事项：

你应该把链表中的每一个节点封装为一个类/结构体。每个节点包含一个数据元素和一个后继指针。
你应该把每一个单链表也封装成为一个结构体。
为防止内存泄漏，你需要在程序最后释放所有申请的堆空间。
不要修改 LinkList 类以外的代码。

输入格式

第一行两个数 $len$ 和 $m$ 表示链表数组长度和总操作数。

接下来的 $m$ 行，每行包含第一个数 $op$ 表示操作类型，后面紧跟两个正整数，表示题目中的 $s_1$, $s_2$。保证操作合法且所给部分和所给要求不会产生超时问题。

输出格式

对于每个操作 1，输出一行一个正整数，表示查询的结果。

样例输入

4 9 0 0 5 0 0 3 1 0 0 1 0 2 0 1 4 2 1 0 1 1 1 1 1 0 1 0 0

样例输出

3 -1 4 3 -1

数据范围

对于 30% 的数据，$len = 1$。

对于 60% 的数据，不包含操作2。

对于 100% 的数据，$1 \leq len \leq 100$，数组中元素小于等于$10 ^ 9$。

使用与题目要求不同的方法或没有使用Sample Code代码通过测试点，会扣除相应测试点的分数
存在内存泄漏会额外扣除20分
同时，此题需要你注意提交代码的代码风格！！！极为糟糕的代码风格（例如改变语法的某些宏定义）会酌情扣分！！！

本题只有一次提交机会！！！

Sample Code

```c++

include

class LinkList { //TODO };

class LinkListArray { private: int len; LinkList **lists;

public: LinkListArray(int n): len(n) { lists = new LinkList*[n]; for (int i = 0; i < n; ++i) lists[i] = new LinkList; } ~LinkListArray() { for (int i = 0; i < len; ++i) { delete lists[i]; } delete []lists; }

void insertNumber(int n, int x) {
    lists[n]->push(x);
}
int queryNumber(int n, int k) {
    return lists[n]->getKth(k);
}
void mergeLists(int p, int q) {
    lists[p]->merge(lists[q]);
}

};

int main() { int len, m; scanf("%d%d", &len, &m); LinkListArray a = LinkListArray(len); for (int i = 0, op, s1, s2; i < m; ++i) { scanf("%d%d%d", &op, &s1, &s2); if (op == 0) { a.insertNumber(s1, s2); } if (op == 1) { printf("%d\n", a.queryNumber(s1, s2)); } if (op == 2) { a.mergeLists(s1, s2); } } return 0; }

```

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！