L2-022. 重排链表

#include <iostream>
#include <cstdio>
using namespace std;

int nextArray[100010]; // 保存每个下标所代表节点的下一个节点地址所在下标 
int dataArray[100010]; // 保存每个下标所代表的节点储存的数据值 
int addArray[100010]; // 顺序储存链表从头到尾的所有节点地址 

int main() {
    int n, start, endAddr, add, currentData, nextAdd;
    cin >> start >> n;
    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &add, &currentData, &nextAdd);
        // 如果 add 的下一个节点地址为 -1, 证明 add 为链表最后一个节点地址 
        if (nextAdd == -1) {
            endAddr = add;
        }
        // 将当前节点的下一个节点地址和当前节点的值保存在对应的数组中
        nextArray[add] = nextAdd;
        dataArray[add] = currentData;
    }
    // 顺序遍历链表，将节点地址顺序储存在 addArray 数组中 
    int length = 1;
    int startCopy = start;
    for (; startCopy != -1; length++) {
        addArray[length] = startCopy;
        startCopy = nextArray[startCopy]; 
    }
    // 按照题目要求的顺序输出 
    nextAdd = addArray[--length];
    for (int i = 1; i <= length; i++) {
        printf("%05d %d ", nextAdd, dataArray[nextAdd]);
        if (i != length) {
            printf("%05d\n", addArray[(i&1?i/2+1:length-i/2)]);
            nextAdd = addArray[(i&1?i/2+1:length-i/2)];
        } else {
            printf("-1\n");
            break; 
        }
    }

    return 0;
}