L2-022 重排链表 (25 分)

最新推荐文章于 2025-04-02 19:24:41 发布

lovesickman

最新推荐文章于 2025-04-02 19:24:41 发布

阅读量190

点赞数

分类专栏： PAT天梯文章标签：链表数据结构算法

本文链接：https://blog.csdn.net/hacker__man/article/details/123561083

版权

PAT天梯专栏收录该内容

21 篇文章

订阅专栏

给定一个单链表$ L_1→L_2→⋯→L_{n−1}→L_n$，请编写程序将链表重新排列为 $L_n→L_1→L_{n−1}→L_2→⋯。$ 例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N (≤105)。结点的地址是5位非负整数，NULL地址用−1表示。

接下来有N行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过105的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

68237 6 00100
00100 1 99999
99999 5 12309
12309 2 00000
00000 4 33218
33218 3 -1

学会了直接使用id寻址，方便了巨多。

/*
A: 10min
B: 20min
C: 30min
D: 40min
*/ 
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <vector>
#include <sstream>
#define pb push_back 
#define all(x) (x).begin(),(x).end()
#define mem(f, x) memset(f,x,sizeof(f)) 
#define fo(i,a,n) for(int i=(a);i<=(n);++i)
#define fo_(i,a,n) for(int i=(a);i<(n);++i)
#define debug(x) cout<<#x<<":"<<x<<endl;
#define endl '\n'
using namespace std;
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

template<typename T>
ostream& operator<<(ostream& os,const vector<T>&v){for(int i=0,j=0;i<v.size();i++,j++)if(j>=5){j=0;puts("");}else os<<v[i]<<" ";return os;}
template<typename T>
ostream& operator<<(ostream& os,const set<T>&v){for(auto c:v)os<<c<<" ";return os;}
template<typename T1,typename T2>
ostream& operator<<(ostream& os,const map<T1,T2>&v){for(auto c:v)os<<c.first<<" "<<c.second<<endl;return os;}
template<typename T>inline void rd(T &a) {
    char c = getchar(); T x = 0, f = 1; while (!isdigit(c)) {if (c == '-')f = -1; c = getchar();}
    while (isdigit(c)) {x = (x << 1) + (x << 3) + c - '0'; c = getchar();} a = f * x;
}

typedef pair<int,int>PII;
typedef pair<long,long>PLL;

typedef long long ll;
typedef unsigned long long ull; 
const int N=1e5+10,M=4e5+10;
/*
19点23分
*/
int h;
struct Node{
    int val,next;
    int id;
}node[N];
int n,idx;
map<int,int>mp;//通过id映射地址
void solve(){
    cin>>h>>n;
    for(int i=1;i<=n;i++){
        int add;cin>>add;
        cin>>node[add].val>>node[add].next;
    }
    for(int i=h;~i;i=node[i].next){
        node[i].id=++idx;
        mp[idx]=i;
    }
    //知道了每个节点的id
    bool flag=1;
    for(int i=idx,j=1;i>=j;){
        if(flag){
            int ID=mp[i--];
            if(mp[j]==ID){
                printf("%05d %d %d\n",ID,node[ID].val,-1);
            }
            else
                printf("%05d %d %05d\n",ID,node[ID].val,mp[j]);
            flag=0;
        }
        else{
            int ID=mp[j++];
            if(mp[i]==ID){
                printf("%05d %d %d\n",ID,node[ID].val,-1);
            }
            else
                printf("%05d %d %05d\n",ID,node[ID].val,mp[i]);
            flag=1;
        }
    }
}

int main(){
    solve();
    return 0;
}