PAT 天梯赛练习集 L2-022. 重排链表
2024-08-31 11:59:48
题目链接:https://www.patest.cn/contests/gplt/L2-022
给定一个单链表 L1→L2→...→Ln-1→Ln,请编写程序将链表重新排列为 Ln→L1→Ln-1→L2→...。例如:给定L为1→2→3→4→5→6,则输出应该为6→1→5→2→4→3。
输入格式:
每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数,即正整数N (<= 105)。结点的地址是5位非负整数,NULL地址用-1表示。
接下来有N行,每行格式为:
Address Data Next
其中Address是结点地址;Data是该结点保存的数据,为不超过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 这个的坑点在它没有和你说所有的点一定都是在同一个链表上的,所以最后遍历的时候用存储的长度而不是题目给的n;
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define eps 0.00000001
#define pn printf("\n")
using namespace std;
typedef long long ll; const int maxn = 1e5+;
int z, n;
struct node{
int d, k, nx;
}p[maxn];
vector <int> vi; int main()
{
scanf("%d%d",&z,&n);
for(int i=;i<n;i++)
{
int d;
scanf("%d",&d);
p[d].d = d;
scanf("%d%d",&p[d].k,&p[d].nx);
}
int s = z;
while(p[s].nx != -)
{
vi.push_back(s);
s = p[s].nx;
}
vi.push_back(s);
for(int i=;i<vi.size();i++)
{
if(i&)
{
printf("%05d %d ", p[vi[i/]].d, p[vi[i/]].k);
if(i != vi.size()-) printf("%05d\n", p[vi[vi.size()--(i+)/]].d);
else printf("-1\n");
}
else
{
printf("%05d %d ", p[vi[vi.size()--i/]].d, p[vi[vi.size()--i/]].k);
if(i != vi.size()-) printf("%05d\n", p[vi[(i+)/]].d);
else printf("-1\n");
}
}
}
最新文章
- Volley简单封装
- oracle impdp 导入
- 纯CSS实现tooltip提示框,CSS箭头及形状之续篇--给整个tooltip提示框加个边框
- 【LeetCode OJ】Linked List Cycle
- [C#常用代码]如何把指定文件夹中的文件移动到指定的文件夹
- python发布模块的原理及部分讲解
- C++基础-位运算
- jsp的自定义标签 控制jsp内容显示
- mysql 返回自增id
- 每个java初学者都应该搞懂的问题
- mser 最大稳定极值区域(文字区域定位)算法 附完整C代码
- 关于CKEditor4.5.6的使用,自定义toolbar配置,上传图片案例(SpringMVC+MyBatis案例),自定义行高,去编辑器的中内容,将编辑器中内容设置到指定的位置等
- JavaScript中的定时事件
- webstorm&#39;s interpreter
- Css实战第二天小结
- 杂项-自动化测试工具:Selenium(浏览器自动化测试框架)
- 自然语言交流系统 phxnet团队 创新实训 个人博客 (一)
- 爬虫beautifulsoup实践
- 搭建Squid反向代理服务器
- groups - 显示用户所在的组