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

输入格式：

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

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

Address Data Next

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

思路：

给定一个单链表：

L1 → L2 → L3 → ... → Ln

要求重排为：

Ln → L1 → Ln-1 → L2 → Ln-2 → L3 → ...

也就是：从两头往中间交替取节点，形成折纸式排列。

1→2→3→4→5→6 → 6→1→5→2→4→3

第一步：读入数据并构建链表

st.nextToken(); int head = (int)st.nval;
st.nextToken(); int N = (int)st.nval;

int[] data = new int[100000], next = new int[100000];
for (int i = 0; i < N; i++) {
    st.nextToken(); int a = (int)st.nval;
    st.nextToken(); data[a] = (int)st.nval;
    st.nextToken(); next[a] = (int)st.nval;
}

• 使用 StreamTokenizer 快速读取整数
• 用两个数组 data[] 和 next[] 存储每个地址对应的数据和下一个地址

第二步：遍历链表，提取真实顺序

int[] list = new int[N], res = new int[N];
int size = 0;
for (int cur = head; cur != -1; cur = next[cur]) 
    list[size++] = cur;

• 从 head 出发，沿着 next 指针一路走到 -1
• 把访问到的地址依次存入 list 数组
• 得到原始链表顺序：[L1_addr, L2_addr, ..., Ln_addr]

 即可得到有效节点的线性序列，忽略输入顺序和无效节点

第三步：双指针重排

int l = 0, r = size - 1;
boolean fromEnd = true;
for (int i = 0; i < size; i++) {
    res[i] = fromEnd ? list[r--] : list[l++];
    fromEnd = !fromEnd;
}

• 左指针 l 从开头出发（L1, L2, ...）
• 右指针 r 从末尾出发（Ln, Ln-1, ...）
• 交替选择：先取右（Ln），再取左（L1），再取右（Ln-1），再取左（L2）...
• 结果存入 res[]：[Ln, L1, Ln-1, L2, ...]

目的：构造目标排列顺序

类比：像折纸一样，把链表从中间对折，然后从外向内展开。

第四步：重建链表并输出

StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
    int a = res[i], d = data[a], n = i == size - 1 ? -1 : res[i+1];
    format(sb, a); sb.append(' ').append(d).append(' ');
    if (n == -1) sb.append("-1\n");
    else { format(sb, n); sb.append('\n'); }
}
System.out.print(sb);

• 遍历 res[] 中的新顺序
• 对每个节点：
  • 获取地址 a、数据 d、下一地址 n
  • 调用 format(sb, a) 手动将整数补零成 5 位字符串
  • 将所有内容追加到 StringBuilder
• 最后一次性输出整个字符串

关于手写format

    static void format(StringBuilder sb, int x) {
        sb.append((char)(x/10000+'0'))
          .append((char)((x/1000)%10+'0'))
          .append((char)((x/100)%10+'0'))
          .append((char)((x/10)%10+'0'))
          .append((char)(x%10+'0'));
    }

题目要求地址是 5 位非负整数，如 00100、00001，不能输出 1

把一个整数（如 1）转换成一个 5 位数字字符串（如 "00001"），并直接追加到 StringBuilder 中，不创建任何中间字符串。没有调用 String.format("%05d", x) 或 printf，这些函数内部要解析格式字符串，非常慢。

完整实现：

import java.io.*;

public class Main {
    private static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    public static void main(String[] args) throws Exception {
        st.nextToken(); int head = (int)st.nval;
        st.nextToken(); int N = (int)st.nval;

        int[] data = new int[100000], next = new int[100000];
        for (int i = 0; i < N; i++) {
            st.nextToken(); int a = (int)st.nval;
            st.nextToken(); data[a] = (int)st.nval;
            st.nextToken(); next[a] = (int)st.nval;
        }

        int[] list = new int[N], res = new int[N];
        int size = 0;
        for (int cur = head; cur != -1; cur = next[cur]) list[size++] = cur;

        int l = 0, r = size - 1;
        boolean fromEnd = true;
        for (int i = 0; i < size; i++) {
            res[i] = fromEnd ? list[r--] : list[l++];
            fromEnd = !fromEnd;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
            int a = res[i], d = data[a], n = i == size - 1 ? -1 : res[i+1];
            format(sb, a); sb.append(' ').append(d).append(' ');
            if (n == -1) sb.append("-1\n");
            else { format(sb, n); sb.append('\n'); }
        }
        System.out.print(sb);
    }

    static void format(StringBuilder sb, int x) {
        sb.append((char)(x / 10000 + '0'))
          .append((char)((x / 1000) % 10 +'0'))
          .append((char)((x / 100) % 10 +'0'))
          .append((char)((x / 10) % 10 + '0'))
          .append((char)(x % 10 + '0'));
    }
}