算法 线性结构3 Reversing Linked List

线性结构3 Reversing Linked List"/>

算法 线性结构3 Reversing Linked List

全部每周作业和视频思考题答案和解析 见 浙江大学 数据结构 思考题+每周练习答案汇总

题目：Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10​5​​) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

给定一个常数K和一个单链链表L，你应该把L上每个K元素的链结颠倒。例如，给定L为1→2→3→4→5→6，如果K=3，那么你必须输出3→2→1→6→5→4；如果K=4，你必须输出4→3→2→1→5→6。

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行包含第一个节点的地址、节点总数的正N（<105）和要反转的子列表的长度的正K（<N）。节点的地址是一个5位非负整数，空值用-1表示。

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

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

Sample Output:

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

解答：

解法1：

这里还是先说一下用链表怎么实现的：首先得通过遍历，把数据按照地址连起来。同时保存每个数据点所在的位置。

然后反转。反转完以后，注意把链表上每个结构体的指向进行修改（注意每个数据的地址是肯定不会变的，但是它指向的下一个数据的地址是会变的）

上面也说了，这种做法得不偿失，主要得不偿失之处在于通过遍历把数据按照地址连起来，超级浪费时间，暂时没找到什么好办法。

解法2：

这是现在我要介绍的第2种解法：

已知结点是五位的非负数，因为一个节点包含三个信息：当前位置，数值，下一个位置。所以我们直接建立两个大数组，用索引代表当前位置，并使用这两个数组来存，一个存它的数据大小，另一个存它的下一个地址：

#include<iostream>
#define MaxSize 100001
using namespace std;
int main() {int data[MaxSize];int link[MaxSize];int head, N, K;cin >> head >> N >> K;for (int i = 0;i<N;i++) {int address, dataPoint, linkPoint;cin >> address >> dataPoint >> linkPoint;data[address] = dataPoint;link[address] = linkPoint;}system("pause");return 0;
}

然后考虑一下反转以后的效果：

为了方便反转，我们直接用另一个数组给它排序：

注意这里的思路是把地址记录下来（因为如果地址是连续的，反转地址以后也可以直接把表当成数组使用）

	int count = 0;  //计数int sortList[MaxSize]; //最大情况while (head != -1) {sortList[count++] = head;head = link[head];}//注意这个时候的链表count 是 等于N的。

然后排序：

	//注意这里，如果加到大于count了，说明超过了。剩下的几个数据不再反转for (int i = 0; i<count-count%K ;i += K) { //反转链表for (int j = 0;j<K / 2;j++) {  int t = sortList[i + j];// 当K = 4, 0要和3交换，1要和2交换，算一下可知相当于 i+j索引元素与i+K -j-1 进行交换sortList[i + j] = sortList[i + K - j - 1];sortList[i + K - j - 1] = t;}}

最后输出就行了：注意输出格式有坑。

	//输出格式这里是个大坑！for (int i = 0;i<count - 1;i++)//cout << sortList[i] <<" "<< data[sortList[i]] <<" "<< sortList[i + 1]<<endl;printf("%05d %d %05d\n", sortList[i], data[sortList[i]], sortList[i + 1]);//cout << sortList[count - 1] <<" "<< data[sortList[count - 1]]<<" " << -1<<endl;/**/printf("%05d %d -1\n", sortList[count - 1], data[sortList[count - 1]]);

完整代码：

#include<iostream>
using namespace std;
#define MaxSize 100001
#include<stdio.h>int main() {int data[MaxSize];int link[MaxSize];int head, N, K;cin >> head >> N >> K;for (int i = 0;i<N;i++) {int address, dataPoint, linkPoint;cin >> address >> dataPoint >> linkPoint;data[address] = dataPoint;link[address] = linkPoint;}int count = 0;  //计数int sortList[MaxSize]; //最大情况while (head != -1) {sortList[count] = head;head = link[head];count++;}//注意这个时候的链表count 是 等于N的。//注意这里，如果加到大于count了，说明超过了。剩下的几个数据不再反转//比如count=14 ,K=4,则反转组为 0-3 4-7 8-11 不反转组为12-13//所以i必须要加到8以后，再加4则for判断失败退出循环。即小于14 - 2判断正确。for (int i = 0; i<count-count%K ;i += K) { //反转链表for (int j = 0;j<K / 2;j++) {  int t = sortList[i + j];// 当K = 4, 0要和3交换，1要和2交换，算一下可知相当于 i+j索引元素与i+K -j-1 进行交换sortList[i + j] = sortList[i + K - j - 1];sortList[i + K - j - 1] = t;}}//输出格式这里是个大坑！for (int i = 0;i<count - 1;i++)//cout << sortList[i] <<" "<< data[sortList[i]] <<" "<< sortList[i + 1]<<endl;printf("%05d %d %05d\n", sortList[i], data[sortList[i]], sortList[i + 1]);//cout << sortList[count - 1] <<" "<< data[sortList[count - 1]]<<" " << -1<<endl;/**/printf("%05d %d -1\n", sortList[count - 1], data[sortList[count - 1]]);system("pause");return 0;
}

编译完全通过。

解法3：我还是尝试用链表做了一下，但是最终也只能归结到类似方法二按照数组的方法，建立了100000个结构体的数组。然后进行反转操作，这样的方法不但没有节约内存反而增加了程序复杂度。

总之，我一直没有想到什么很好的纯链表反转的解决思路。看了一些别人写的方法也都是建立大数组。此题待定，希望以后能有更好的方法。（不过既然用五位数来存地址了，可能冥冥之中告诉了题目就是要用五位数的数组吧）