PAT甲级1074 Reversing Linked List (25分)

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3AxOTY3OTE0OTAx_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/68f1ec52904741c39483a400bc0da13c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3AxOTY3OTE0OTAx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/f72c1eeb516d48cd84b5ef5cd826eec7.png