模拟
$O(n)$
复杂的模拟总是有一颗简单的内心
初看这道题似乎真的感觉代码不好写,但是仔细分析,会发现其实写出来的代码并没有想象的那么复杂。
解题步骤:
- 输入所有节点信息,并且将链表内所有的结点的地址(便于后期查找)加到一个数组里(在链表中操作会麻烦的多,不 如在数组里操作)。
- 用一个数组存储反转后的地址(这个地址就是刚刚步骤一的数组中的地址)
- 按该次序输出地址和值
细节就看我代码里怎么写吧:
AC code
#include<iostream>
#include<vector>
using namespace std;
const int N=100010;
int e[N],ne[N];
int main()
{
int head,n,m; cin>>head>>n>>m;
for(int i=0;i<n;i++)
{
int adr;
cin>>adr>>e[adr]>>ne[adr];
}
vector<int> a; //将链表的每一位的地址存入a数组
for(int i=head;~i;i=ne[i]) a.push_back(i);
n=a.size();
int res[N],k=n-1;
for(int i=0;i<n;i+=m)
{
int j=min(n,i+m)-1;
while(j>=i) res[k--]=a[j--]; //再将这些地址进行反转
}
for(int i=0;i<n;i++)
{
printf("%05d %d ",res[i],e[res[i]]);
if(i==n-1) puts("-1");
else printf("%05d\n",res[i+1]); //如果不是最后一位,就输出下一位的地址
}
return 0;
}