PAT乙级 1025 反转链表 (25 分)

叁歲伎倆 2023-06-12 11:23 26阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
1.先利用map读入数据，键值为每个结点地址  
2.从第初始键值开始，依次遍历之后的每个结点，并存入向量数组，当遍历到next地址是-1时停止往下，因为题目中描述了链表的末尾是-1  
3.最后按题目要求依次反转k的倍数个结点  
4.最后输出的时候因为要重新连接成一个新的链表，但是向量数组中存的下一个地址并不是，所以nxet地址不能直接用当前地址的next地址输出，输出下一个结点的地址即可

下面是第一次写的代码，想到哪里写到哪里，结构很乱，各种数据定义也很多，时间复杂度太高

#include<iostream>
    #include<vector>
    #include<unordered_map>
    using namespace std;
    struct node{ 
        string add,next;
        int data;
    };
    int main()
    { 
        int n,k,flag=1;
        string begin;
        cin>>begin>>n>>k;
        vector<node> nn(n);
        unordered_map<string,node> result;
        for(int i=0;i<n;i++)
        { 
            string a,b;
            int c;
            cin>>a>>c>>b;
            result[a].data=c;
            result[a].next=b;
        }
        int cnt=n-1;
        nn[0].add=begin;
        nn[0].next=result[begin].next;
        nn[0].data=result[begin].data;
        while(cnt--)
        { 
            nn[n-1-cnt].add=nn[n-2-cnt].next;
            nn[n-1-cnt].next=result[nn[n-1-cnt].add].next;
            nn[n-1-cnt].data=result[nn[n-1-cnt].add].data;
        }
        int pre=0;
        vector<node> shuchu(n);
        cnt=0;
        for(int i=k;pre<n;i+=k)
        { 
            if(i>n)
            { 
                flag=0;
                i=n;
            }
            if(flag)
            { 
                for(int j=i;j>pre;j--)
                { 
                    shuchu[cnt].add=nn[j-1].add;
                    shuchu[cnt].data=nn[j-1].data;
                    cnt++;
                }
            }
            else 
            { 
                for(int j=pre;j<i;j++)
                { 
                    shuchu[cnt].add=nn[j].add;
                    shuchu[cnt].data=nn[j].data;
                    cnt++;
                }
            }
            pre=i;
        }
        for(int i=0;i<n;i++)
        { 
            cout<<shuchu[i].add<<" "<<shuchu[i].data<<" ";
            if(i!=n-1)
            cout<<shuchu[i+1].add<<endl;
            else 
            cout<<"-1"<<endl;
        }
        return 0;
    }

下面是学习大佬写的优质代码后改进的：

#include<iostream>
    #include<vector>
    #include<unordered_map>
    #include<algorithm>
    using namespace std;
    struct node{ 
        string add,next;
        int data;
    };
    int main()
    { 
        int n,k;
        string begin;
        cin>>begin>>n>>k;
        vector<node> nn(n+5);
        unordered_map<string,node> result;
        for(int i=0;i<n;i++)//读入数据
        { 
            string a,b;
            int c;
            cin>>a>>c>>b;
            result[a].data=c;
            result[a].next=b;
        }
        for(int i=0;i<n;i++)
        { 
            nn[i].add=begin;
            nn[i].data=result[begin].data;
            nn[i].next=result[begin].next;
            begin=result[begin].next;
            if(begin=="-1")//已经到链表末尾
            { 
                n=i+1;
            }
            if((i+1)%k==0)//加上当前结点，刚好构成k个结点，反转
            { 
                reverse(nn.begin()+i+1-k,nn.begin()+i+1);
            }
        }
        for(int i=0;i<n;i++)
        { 
            cout<<nn[i].add<<" "<<nn[i].data<<" ";//printf("%s %d ",&nn[i].add,nn[i].data);
            if(i!=n-1)cout<<nn[i+1].add<<endl;
            else 
            cout<<"-1"<<endl;
        }
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191112210843317.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw==,size_16,color_FFFFFF,t_70