【CCCC】L2-022 重排链表 (25分)，链表遍历

problem

L2-022 重排链表 (25分)
给定一个单链表 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 (≤10
​5
​​ )。结点的地址是5位非负整数，NULL地址用−1表示。

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

Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过10
​5
​​ 的正整数；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

solution

• 题意：给出链表L为1→2→3→4→5→6，将其重排为6→1→5→2→4→3并输出。
• 把原始链表数据先存下来，然后再按顺序遍历一遍即可。
• 样例4有毒，可能存在不在链表上的点，所以输入后还得自己跑一遍链表长度。

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

struct node{ int address, data, next;}li[maxn];
vector<node>l1, l2;

int main(){
    int begin, n;
    cin>>begin>>n;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;  li[x].address = x;
        cin>>li[x].data>>li[x].next;
    }
    //数据比较坑（第4个点），可能存在不再一个链表上的两个结点,所以要记录链表长度
    int mid = n/2, cnt = 0;
    for(int i = begin; i != -1; i=li[i].next)cnt++;
    mid = cnt/2, cnt = 0;
    for(int i = begin; i != -1; i=li[i].next){
        //cout<<i<<"\n";
        cnt++;
        if(cnt<=mid){
            l1.push_back(li[i]);
        }else{
            l2.push_back(li[i]);
        }
    }
    for(int i=0,j=l2.size()-1; i<l1.size() && j>=0; i++,j--){
        //cout<<i<<" "<<j<<endl;
        printf("%05d %d ", l2[j].address,l2[j].data);
        printf("%05d\n", l1[i].address);
        printf("%05d %d ", l1[i].address,l1[i].data);
        if(j!=0)printf("%05d\n", l2[j-1].address);
        else printf("-1\n");
    }
    if(cnt%2==1){
        printf("%05d %d ",l2[0].address,l2[0].data);
        printf("-1\n");
    }
    return 0;
}