L2-022 重排链表 - 团体程序设计天梯赛-练习集

这是一道模拟链表，给链表地址重新指向的题，考察对链表操作的熟悉使用。

我们先顺序访问一遍题目给的链表，用数组存时间戳上的链表地址，然后按题目要求去构造，通过控制奇偶来进行构造新链表即可。

ac code + 注释

#include<bits/stdc++.h>
using namespace std;
const int N = 100001;

struct node{
    int data;   //节点信息
    int nextx;  //下一个地址
}arr[N];

void solve(){
    int start,n;cin>>start>>n;
    for(int i = 1;i<=n;++i){    //初始化每个节点信息
        int address,data,nextx;
        cin>>address>>data>>nextx;
        arr[address].data = data;
        arr[address].nextx = nextx;
    }
    vector<int>idx(n+1);    //获取顺序链表的每一个访问顺序地址
    int s = start;          //开始的链头
    int id = 1;
    while(s!=-1){
        idx[id++] = s;
        s = arr[s].nextx;
    }
    n = id - 1;             //考虑有多出来的节点，所以链表长度不一定为n
    int r = n,l = 1;
    int t = 0;
    while(l<r){
        if(!t){             //根据题目要求，分开奇数操作和偶数操作
            int start_address = idx[r];
            int end_address = idx[l];
            arr[start_address].nextx = end_address;
            r--;
        }else{
            int start_address = idx[l];
            int end_address = idx[r];
            arr[start_address].nextx = end_address;
            l++;
        }
        t^=1;
    }
    arr[idx[r]].nextx = -1;         //将重新构造的链表的链尾指向空
    int new_start = idx[n];         //因为构造出来的头是原本的顺序链表的尾部，所以获取原来顺序链表的最后一个节点位置做链头
    
    while(new_start!=-1){           //然后从队头开始访问链表，按要求打印
        cout<<setw(5)<<setfill('0')<<new_start<<' ';
        cout<<arr[new_start].data<<' ';
        if(arr[new_start].nextx==-1)cout<<arr[new_start].nextx<<endl;
        else cout<<setw(5)<<setfill('0')<<arr[new_start].nextx<<endl;
        new_start = arr[new_start].nextx;
    }
}

int main(){
    solve();
}