L2-022. 重排链表

时间限制

500 ms

内存限制

65536 kB

代码长度限制

8000 B

判题程序

Standard

作者

陈越

给定一个单链表 L₁→L₂→...→L_n-1→L_n，请编写程序将链表重新排列为 L_n→L₁→L_n-1→L₂→...。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

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

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

Address Data Next

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

不会链表的渣渣，各种STL... 模拟

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<string>

#include<map>

#include<vector>

#include<deque>

#include<algorithm>

#define MAX 100005

using namespace std;

struct rec{

    char add[];

    int dat;

    char nex[];

}rec[MAX];

struct Node{

    char add[];

    int dat;

}node;

vector<Node> v[MAX];

deque<Node> q;

int main()

{

    int t,n,i;

    char add[];

    map<string,int> mpadd;

    map<string,int> mpdat;

    scanf(" %s %d",add,&n);

    t=;

    for(i=;i<=n;i++){

        scanf(" %s %d %s",rec[i].add,&rec[i].dat,rec[i].nex);

        if(!mpadd[rec[i].add]) mpadd[rec[i].add]=++t;

        if(!mpdat[rec[i].add]) mpdat[rec[i].add]=rec[i].dat;

        if(!mpadd[rec[i].nex]) mpadd[rec[i].nex]=++t;

    }

    for(i=;i<=n;i++){

        strcpy(node.add,rec[i].nex);

        node.dat=mpdat[rec[i].nex];

        v[mpadd[rec[i].add]].push_back(node);

    }

    while(strcmp(add,"-1")!=){

        strcpy(node.add,add);

        node.dat=mpdat[add];

        q.push_back(node);

        strcpy(add,v[mpadd[add]][].add);

    }

    int c=;

    while(q.size()){

        c++;

        if(c==){

            printf("%s %d",q.back().add,q.back().dat);

            q.pop_back();

        }

        else if(c&){

            printf(" %s\n%s %d",q.back().add,q.back().add,q.back().dat);

            q.pop_back();

        }

        else{

            printf(" %s\n%s %d",q.front().add,q.front().add,q.front().dat);

            q.pop_front();

        }

    }

    printf(" -1\n");

    return ;

}

巴特西

GPLT天梯赛 L2-022. 重排链表

L2-022. 重排链表

最新文章

热门文章