PAT甲级1074 Reversing Linked List (25分)

时间:2022-10-31 04:06:54

PAT甲级1074 Reversing Linked List (25分)
PAT甲级1074 Reversing Linked List (25分)【程序思路】
先根据地址按顺序读入节点,入栈,当栈里的元素个数等于k时全部出栈,并按出栈顺序保存,最后若栈不为空,则全部出栈并按出栈的稀饭顺序保存,最后输出各节点
注意:输入的节点中有可能存在无用节点需要过滤,这里我使用map映射来实现过滤
【代码实现】

#include<bits/stdc++.h>
using namespace std;
struct node{
int addrest,data,next;
}t;
int stk[100005];
int main(){
map<int,node> a;
vector<int> c;
int head,n,i,k,top = -1;
cin>>head>>n>>k;
for(i=0;i<n;i++) {
cin>>t.addrest>>t.data>>t.next;
a[t.addrest] = t;
}
while(head!=-1) {
stk[++top] = head;
if(top + 1 == k)
while(top != -1)
c.push_back(stk[top--]);
head = a[head].next;
}
for(i = 0; i <= top; i++)
c.push_back(stk[i]);
for (i = 0; i < c.size() - 1; i++)
printf("%05d %d %05d\n",c[i],a[c[i]].data,c[i+1]);
printf("%05d %d -1\n",c[i],a[c[i]].data);
return 0;
}