单链表反转排列：算法详解与代码实现

问题描述： 给定一个单链表 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 (≤10⁵)。结点的地址是5位非负整数，NULL地址用-1表示。

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

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

代码实现 (C语言)：

#include<stdio.h>
#include<stdlib.h>
struct LNode{
    long data;
    long Next;
}LNodes[100010];
int main(){
    long head_address,N;
    scanf('%ld %ld',&head_address,&N);
    for(int i=0;i<N;i++){
        long address;
        scanf('%ld',&address);
        scanf('%ld %ld',&LNodes[address].data,&LNodes[address].Next);
    }
    long Seq[N];
    long p = head_address;
    int num = 0;
    while(p != -1){
        Seq[num++] = p;
        p = LNodes[p].Next;
    }
    int next=0,pre=num-1,tmp = 0;
    while(num--){
        printf('%05ld %ld ',Seq[pre],LNodes[Seq[pre]].data);
        tmp = tmp < pre ? --pre : ++pre;
        if(num == 0){
            printf('-1\n');
            break;
        }
        printf('%05ld\n',Seq[next]);
        pre = next;
        next = tmp;
    }
}

算法思路:

构建链表: 程序首先读入链表的头结点地址和结点总个数，然后根据结点的地址、数据和下一结点的地址构建链表。
存储结点地址: 程序遍历链表，将每个结点的地址依次存储在一个数组Seq中。
反转排列: 程序使用双指针的方式重新排列链表的顺序。
- pre 指针指向数组中最后一个结点，next 指针指向数组中第一个结点。
- 循环遍历数组，依次输出 pre 指向的结点，然后更新 pre 指针。如果 pre 指针已经到达数组边界，则更新为下一个结点。
- 同时输出 next 指向的结点，然后更新 next 指针。如果 next 指针已经到达数组边界，则更新为上一个结点。
输出结果: 最后，程序根据题目要求，按照顺序输出每个结点的地址、数据和下一结点的地址。

数据结构:

LNode 结构体表示链表中的结点，包含两个成员变量：
- data: 存储结点的数据。
- Next: 存储下一个结点的地址。
LNodes 数组存储所有结点，数组下标对应结点地址。
Seq 数组存储所有结点的地址，用于实现反转排列。

程序中的关键变量:

head_address: 链表头结点地址。
N: 链表中结点的总个数。
p: 遍历链表的指针。
num: 链表中结点的数量。
next: 当前结点的下一个结点在 Seq 数组中的索引。
pre: 当前结点的前一个结点在 Seq 数组中的索引。
tmp: 用于保存 pre 和 next 的临时值。

示例输入和输出:

输入：

00001 6
00001 1 00002
00002 2 00003
00003 3 00004
00004 4 00005
00005 5 00006
00006 6 -1

输出：

00006 6 00001
00001 1 00005
00005 5 00002
00002 2 00004
00004 4 00003
00003 3 -1

总结:

该程序实现了将单链表反转排列的功能，通过使用双指针的方式，有效地解决了问题。代码逻辑清晰易懂，结构合理，并提供了详细的注释，方便读者理解。