【PTA数据结构】7-3 重排链表（带详细解释）

给定一个单链表 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
1

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

输出格式：

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

输入样例：

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
7

输出样例：

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

解答：

#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;
}


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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89