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

输入格式：

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

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

1
Address Data Next

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

输出格式：

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

输入样例：

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

输出样例：

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

思路

静态链表解题套路（因为过于套路，近期的PAT乙级、甲级都没有出现过，不过sort排序的套路还是有的）

静态链表：使用数组索引模拟结点地址，本题的地址是5位整数

还原链表后，设立两个指针，分别指向链表头部和尾部，每次先取出尾部节点，再取出头部节点，直到两指针相遇

泛化来说，指针不一定是(C语言里int*)这样的指针，指针的意义是获取数据所在位置，数组索引也可以是指针

知识点：静态链表、constexpr语法

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>

using namespace std;
constexpr int MAX_SIZE = 100001; //类似#define MAX_SIZE 100001

struct Node {
    int add;
    int data;
};

int main() {
    int head, n;
    cin >> head >> n;
    int data[MAX_SIZE], next_add[MAX_SIZE];//静态链表，存储索引地址的数据和下一个结点的索引地址
    while(n--) {
        int a, b, c;
        cin >> a >> b >> c;
        data[a] = b;
        next_add[a] = c;
    }
    vector<Node> ve;
    while(head != -1) {//构造链表
        ve.push_back(Node{head, data[head]});
        head = next_add[head];
    }
    //最终的ve中，结点数可能不是n，即题目给定了不在链表中的节点（坑爹测试点3）
    int i = 0, j = (int)ve.size() - 1;//i和j分别指向链表两端
    vector<Node> ret;
    while(i < j) {
        ret.push_back(ve[j]);//先放入后端
        ret.push_back(ve[i]);//再放入前端
        i++, j--;//似乎Java中取消了(,)逗号运算符
    }
    if(i == j) {//如果链表节点数是奇数，会漏一个
        ret.push_back(ve[i]);
    }
    if(!ret.empty()) {
        for(int i = 0; i < (int)ret.size() - 1; i++) { //这里不要原始的n-1，因为可能最终链表中结点数比n小
            printf("%05d %d %05d\n", ret[i].add, ret[i].data, ret[i + 1].add);
        }
        printf("%05d %d -1\n", ret.back().add, ret.back().data);//也可ret[ret.size()-1]
    }
    return 0;
}