顺序表与链表综合操作

考点定位

本课深化 顺序表与链表综合操作。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

顺序表支持O(1)随机访问但中间插删搬移元素；链表按结点访问为O(n)，已知结点位置后改链可O(1)。选型必须结合访问和修改比例。

算法推演

顺序表删除区间用读写双指针保持稳定；链表合并先设哨兵结点，始终把较小结点摘接到尾部，最后接剩余链。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

处理完前k个输入后，输出区恰好是这k个元素稳定去重后的序列。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：不要把“已知结点指针”和“只知道序号”混为同一种复杂度。

随课应用

输入第一行n，第二行n个整数。保持首次出现顺序，输出去重后的整数，空格分隔。使用Python 3标准输入输出。

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。