PAT 天梯赛 L2-022. 重排链表 【数据结构】
2024-09-04 00:54:10
题目链接
https://www.patest.cn/contests/gplt/L2-022
思路
先用结构体 把每个结点信息保存下来
然后深搜一下 遍历一下整个链表
然后就重新排一下
但是要注意一个坑点 是
有效的结点数 不一定是n 这个原因 导致第三个测试点过不了
意思就是 它给出N 个结点 但是不一定这N个结点 都是在一张链表上的
也就是说 我们需要仅仅是 头结点在的那张链表
因为 它仅仅需要输出 所以 下一个地址 直接输出下一个地址的地址就可以了
而不用 所以操作 重新指向一遍
查了好久。。
AC代码
#include <cstdio>
#include <cstring>
#include <ctype.h>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <stack>
#include <set>
#include <numeric>
#include <sstream>
#include <iomanip>
#include <limits>
#define CLR(a) memset(a, 0, sizeof(a))
#define pb push_back
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair<string, int> psi;
typedef pair<string, string> pss;
const double PI = 3.14159265358979323846264338327;
const double E = exp(1);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const int maxn = 1e6 + 5;
const int MOD = 1e9 + 7;
int pos[maxn];
struct Node
{
int add;
int value;
int next;
}temp;
vector <Node> ans, vis;
map <int, Node> m;
void dfs(int add)
{
vis.pb(m[add]);
if (m[add].next != -1)
dfs(m[add].next);
}
int main()
{
int ini, n;
scanf("%d%d", &ini, &n);
for (int i = 0; i < n; i++)
{
scanf("%d %d %d", &temp.add, &temp.value, &temp.next);
m[temp.add] = temp;
}
dfs(ini);
int l = 0, r = vis.size() - 1;
while (1)
{
if (r < l)
break;
ans.pb(vis[r]);
r--;
if (r < l)
break;
ans.pb(vis[l]);
l++;
}
n = ans.size() - 1;
for (int i = 0; i < n; i++)
printf("%05d %d %05d\n", ans[i].add, ans[i].value, ans[i + 1].add);
printf("%05d %d -1\n", ans[n].add, ans[n].value);
}
最新文章
- AS快捷键
- tomcat session cluster
- Linux内核配置机制(make menuconfig 、Kconfig、Makefile)讲解【转】
- 传Windows 9预览版今秋发布
- React-用ImmutableJS提高性能
- [Head First Python]4.读取文件datafile.txt, 去除两边空格, 存储到列表,从列表格式化(nester.py)后输出到文件man.out,other.out
- SQLSERVER 数据库性能的的基本 MVC + EF + Bootstrap 2 权限管理
- springmvc国际化 基于浏览器语言的国际化配置
- (转)JAVA多线程和并发基础面试问答
- EJB系列 - 消息与MDB
- mybatis返回int类型报null
- 为archlinux选择国内镜像
- in exists
- javascript函数闭包(closure)
- 避免使用jQuery的html方法来替换标签,而是使用replaceWith方法
- 访问www.baidu.com后会发生什么(一次完整的网络通讯过程)
- CodeForces 19B Checkout Assistant
- zw版【转发&#183;台湾nvp系列Delphi例程】HALCON SetIcon2
- Linux内核 TCP/IP参数调优
- PCB 锣板和半孔工艺的差别