L2-2 重排链表 (25 分)

2019/03/12 17:39
阅读数 329

给定一个单链表 L1​​→L2​​→⋯→Ln1​​→Ln​​,请编写程序将链表重新排列为 Ln​​→L1​​→Ln1​​→L2​​→⋯。例如:给定L为1→2→3→4→5→6,则输出应该为6→1→5→2→4→3。

输入格式:

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

接下来有N行,每行格式为:

Address Data Next

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


代码:
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <set>
using namespace std;
struct link {
    int Next,Data;
}l[1000000];
int num[1000000];
int main() {
    int n,data,add,nadd,sadd;
    cin>>sadd>>n;
    for(int i = 0;i < n;i ++) {
        cin>>add>>data>>nadd;
        l[add].Data = data;
        l[add].Next = nadd;
    }
    int c = 0,t = sadd;
    while(t != -1) {
        num[c ++] = t;
        t = l[t].Next;
    }
    for(int i = 1;i <= c;i ++) {
        if(i % 2) t = c - (i + 1) / 2;
        else t = (i - 1) / 2;
        if(i > 1) printf(" %05d\n",num[t]);
        printf("%05d %d",num[t],l[num[t]].Data);
    }
    cout<<' '<<-1;
}

 

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部