【题解 | 双端队列】天梯赛练习集:重排链表

2024-04-17 16:28

本文主要是介绍【题解 | 双端队列】天梯赛练习集:重排链表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

重排链表

给定一个单链表 L 1 → L 2 → . . . → L n − 1 → L n L_1 \to L_2 \to ...\to L_{n-1}\to L_n L1L2...Ln1Ln,将其重新排列后变为 L 1 → L n → L 2 → L n − 1 → L 3 → L n − 2 . . . L_1 \to L_n \to L_2 \to L_{n-1} \to L_3 \to L_{n-2} ... L1LnL2Ln1L3Ln2...,例如:给定 L L L 1 → 2 → 3 → 4 → 5 → 6 1→2→3→4→5→6 123456 ,则输出应该为 6 → 1 → 5 → 2 → 4 → 3 6→1→5→2→4→3 615243

输入格式:

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数,即正整数 N ( ≤ 1 0 5 ) N (≤10^5 ) N(105)。结点的地址是5位非负整数,NULL地址用−1表示。

接下来有N行,每行格式为:

Address Data Next

其中Address是结点地址;Data是该结点保存的数据,为不超过 1 0 5 10^5 105 的正整数;Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式:

对每个测试用例,顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。

输入样例:

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例:

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

解题思路:

这个问题可以通过使用双端队列来解决。首先,我们将链表中的所有节点按照原始顺序添加到双端队列中。然后,我们交替从双端队列的前端和后端取出节点并将它们连接起来,就得到了所需的链表。

当然,使用两个栈也是一样的。

#include <bits/stdc++.h>
using namespace std;struct Node {int address, data, next;int order = 2 * 100000;  // 初始化节点顺序为一个较大的数
} nodes[100000];// 比较函数,用于按照节点顺序排序
bool cmp(Node a, Node b) {return a.order < b.order;
}int main() {int begin, n, address;cin >> begin >> n;  // 读取链表开始地址和节点数量for (int i = 0; i < n; i++) {cin >> address;  // 读取节点地址cin >> nodes[address].data >> nodes[address].next;  // 读取节点数据和下一个节点地址nodes[address].address = address;  // 记录节点地址}int count = 0;// 遍历链表,记录节点顺序while (begin != -1) {nodes[begin].order = count++;begin = nodes[begin].next;}// 按照节点顺序排序sort(nodes, nodes + 100000, cmp);deque<Node> dq;// 将节点按照顺序添加到双端队列中for (int i = 0; i < count; i++) {dq.push_back(nodes[i]);}vector<Node> ans;// 交替从双端队列的前端和后端取出节点while (!dq.empty()) {ans.push_back(dq.back());dq.pop_back();if (!dq.empty()) {ans.push_back(dq.front());dq.pop_front();}}// 输出重新排列后的链表for (size_t i = 0; i < ans.size() - 1; i++) {printf("%05d %d %05d\n", ans[i].address, ans[i].data, ans[i + 1].address);}// 输出最后一个节点printf("%05d %d -1\n", ans[ans.size() - 1].address, ans[ans.size() - 1].data);return 0;
}

测试链接:重排链表

这篇关于【题解 | 双端队列】天梯赛练习集:重排链表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/912286

相关文章

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

csu1329(双向链表)

题意:给n个盒子,编号为1到n,四个操作:1、将x盒子移到y的左边;2、将x盒子移到y的右边;3、交换x和y盒子的位置;4、将所有的盒子反过来放。 思路分析:用双向链表解决。每个操作的时间复杂度为O(1),用数组来模拟链表,下面的代码是参考刘老师的标程写的。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2431 poj 3253 优先队列的运用

poj 2431: 题意: 一条路起点为0, 终点为l。 卡车初始时在0点,并且有p升油,假设油箱无限大。 给n个加油站,每个加油站距离终点 l 距离为 x[i],可以加的油量为fuel[i]。 问最少加几次油可以到达终点,若不能到达,输出-1。 解析: 《挑战程序设计竞赛》: “在卡车开往终点的途中,只有在加油站才可以加油。但是,如果认为“在到达加油站i时,就获得了一

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-

RabbitMQ练习(AMQP 0-9-1 Overview)

1、What is AMQP 0-9-1 AMQP 0-9-1(高级消息队列协议)是一种网络协议,它允许遵从该协议的客户端(Publisher或者Consumer)应用程序与遵从该协议的消息中间件代理(Broker,如RabbitMQ)进行通信。 AMQP 0-9-1模型的核心概念包括消息发布者(producers/publisher)、消息(messages)、交换机(exchanges)、

建立升序链表

题目1181:遍历链表 时间限制:1 秒 内存限制:32 兆 特殊判题:否 提交:2744 解决:1186 题目描述: 建立一个升序链表并遍历输出。 输入: 输入的每个案例中第一行包括1个整数:n(1<=n<=1000),接下来的一行包括n个整数。 输出: 可能有多组测试数据,对于每组数据, 将n个整数建立升序链表,之后遍历链表并输出。 样例输

poj3750约瑟夫环,循环队列

Description 有N个小孩围成一圈,给他们从1开始依次编号,现指定从第W个开始报数,报到第S个时,该小孩出列,然后从下一个小孩开始报数,仍是报到S个出列,如此重复下去,直到所有的小孩都出列(总人数不足S个时将循环报数),求小孩出列的顺序。 Input 第一行输入小孩的人数N(N<=64) 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N),用

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

POJ2010 贪心优先队列

c头牛,需要选n头(奇数);学校总共有f的资金, 每头牛分数score和学费cost,问合法招生方案中,中间分数(即排名第(n+1)/2)最高的是多少。 n头牛按照先score后cost从小到大排序; 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi