PAT甲级1074 Reversing Linked List (25分)-蒲公英云

PAT甲级1074 Reversing Linked List (25分)

Dear 丶 2023-07-22 05:59 75阅读 0赞

题目截图
输入输出 【程序思路】
先根据地址按顺序读入节点，入栈，当栈里的元素个数等于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;
}