|
给定一个单链表 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 (≤)。结点的地址是5位非负整数，NULL地址用?1表示。
接下来有N行，每行格式为：
Address Data Next
其中Address是结点地址；Data是该结点保存的数据，为不超过的正整数；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
解答：
#define _CRT_SECURE_NO_WARNINGS
#define MAXSIZE 100001
#define HEADNODE 100000
#include<stdio.h>
typedef struct Node
{
int data; //记录当前结点的数据
int next; //记录下一个结点的地址
}Node;
int main()
{
Node a [MAXSIZE]; //存储链表，下标为结点地址
int add_head, num; //记录第一个结点的地址和结点数量
scanf("%d %d", &add_head, &num);
int init [MAXSIZE];//init(initial)存储原来的结点地址顺序
int renew [MAXSIZE]; //renew存储改变后的结点地址顺序。
int add, data, next;
//输入数据，创建链表
int i = 0;
for (i = 0; i < num; i++)
{
//给地址为add的结点赋值
scanf("%d %d %d", &add, &data, &next);
a [add].data = data;
a [add].next = next;
}
//把初始链表的结点地址按顺序存储到init数组里
int count = 0; //计算一共有多少个有效结点（前面输入的结点可能是不在链表里的“废结点”）
add = add_head;
while (add != -1)
{
init [count] = add;
add = a [add].next;
count++;
}
//这时，有效结点的总个数为count
//把修改后的地址顺序存储到renew里
int init_left = 0, init_right = count - 1; //相当于init的指针
//init_left指向init数组的左侧，init_right指向init的右侧开始，两者往中间靠
int new_point = 0; //相当于renew数组的指针
while (init_left <= init_right)
{
if (init_left < init_right)
{
//把init数组中最后一个结点的地址，赋值给renew数组的第一个元素
renew [new_point] = init [init_right];
new_point++;//指向第二位
init_right--;//指向倒数第二个结点地址
//再把init数组中第一个结点的地址，赋值给renew数组的第二个元素
renew [new_point] = init [init_left];
new_point++; //指向第三位
init_left++; //指向第二个结点的地址
//一次循环相当于给renew传了两个元素，一个是init的最后一位，一个是init的第一位
//当init_left与init_right相遇的时候，循环就退出了
}
else
{
//init_left == init_right
//这时候说明有效结点个数是整数
renew [new_point] = init [init_left];
new_point++;
init_left++;
//这时renew数组的元素就是题目要求的结点顺序
}
}
//按照renew数组的地址顺序打印每个结点的地址和数据
for (i = 0; i < count - 1; i++)
{
//输出的顺序为：当前结点的地址，结点数据，下一结点的地址
//这里要注意的是：这里的“下一结点”已经不是存储在a数组里的a[i].next了（.next对应的是起始链表顺序）
//所以这里输出第三位，应该是renew数组里当前结点的下一个结点地址
printf("%05d %d %05d\n", renew [i], a [renew [i]].data, renew [i + 1]);
}
printf("%05d %d -1\n", renew [i], a [renew [i]].data);
return 0;
}
|