PTA甲级 1074 Reversing Linked List (25分)

强烈推荐,刷PTA的朋友都认识一下柳神–PTA解法大佬

本文由参考于柳神博客写成

柳神的CSDN博客,这个可以搜索文章

柳神的个人博客,这个没有广告,但是不能搜索

还有就是非常非常有用的 算法笔记 全名是

算法笔记  上级训练实战指南		//这本都是PTA的题解
算法笔记

PS 今天也要加油鸭

题目原文

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 (≤105) 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.

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

题目大意:

给你一个链表,然后让你反转这个链表

Address Data Next

格式是这样的.

最后结束的链表的地址是 -1

思路如下:

① 我们可以用静态做-动态难,还麻烦.

node[1000000]的结构体

② 我的想法,就是把地址和数据绑定在一起.

然后输入的地址就直接是node的下标

然后我这个人有点小傻

然后再创建一个node[100000] 的数组来存储我们排序好的数组

③ 然后再创建一个node[100000]的数组来存储我们打乱后的数据.

测试点6 错误

可能结果,你没有考虑到中间节点就断开的情况

例子如下:

00000 6 3
00000 1 11111
11111 2 22222
22222 3 -1
33333 4 44444
44444 5 55555
55555 6 -1

正确结果应该是:

00000 1 11111
11111 2 22222
22222 3 -1

代码如下:

我的代码可能(就是)比较混乱:

  #include<iostream>
using namespace std;
struct Node {int data;int next;
}node[100000],Reall[100000],Fin[100000];
void reverse(struct Node* p, int N, int M);
int main(void) {int Address=0, Data=0, Next = 0,FirstAddress = 0, N=0, K=0,up_N=0,t=0,t_copy=0,i=0;scanf("%d%d%d", &FirstAddress, &N, &K);for (i = 0; i < N; ++i) {scanf("%d%d%d", &Address, &Data, &Next);node[Address].data = Data;node[Address].next = Next;}up_N = FirstAddress;	//t用来保存下标for (i = 0; i < N; ++i) {Reall[i].next = up_N;Reall[i].data = node[up_N].data;up_N = node[up_N].next;if (up_N == -1) { N = ++i; break; }}t = t_copy = K - 1;for ( i = 0; i <=N-1;i=i+K) {for (int j=i; j <= t_copy; j++) {Fin[t] = Reall[j];t--;}t_copy = t_copy + K;t = t_copy;}if (N%K!=0) {for (i = i - K; i < N; i++) Fin[i] = Reall[i];}//cout << "\n\n";for (i = 0; i < N-1; ++i) printf("%05d %d %05d\n", Fin[i].next, Fin[i].data,Fin[i+1].next);printf("%05d %d %d", Fin[i].next, Fin[i].data, -1);return 0;
}

算法笔记的代码

算法笔记鸡贼的地方就在于,算法笔记是没有逆置的,所以算法笔记的输出代码就特别的麻烦.

代码如下:

#include<iostream>
#include<cstdio>
#include <algorithm>
using namespace std;
const int maxn = 100010;
struct Node {int address, data, next;int order;					//结点再链表上的序号,无效的节点记录为maxn
}node[maxn];
bool cmp(Node a, Node b) {return a.order < b.order;
}
int main(void) {for (int i = 0; i < maxn; ++i) {		//初始化node[i].order = maxn;				//初始化全部为无效结点}int begin = 0, n = 0, K = 0, address = 0;scanf("%d%d%d", &begin, &n, &K);for (int i = 0; i < n; ++i) {scanf("%d",&address);scanf("%d%d", &node[address].data, &node[address].next);node[address].address = address;}int p = begin, count = 0;				//count计数有效节点的数目while (p != -1) {node[p].order = count++;			//结点在单链表中的序号p = node[p].next;					//下一个节点}sort(node, node + maxn, cmp);			//按单链表从头到尾的顺序排列//有效节点为前count个节点.为了下面书写方便,因此把count赋值给nn = count;//单链表我们就已经构建好了//cout << "\n\n";//算法笔记比较鸡贼的就是,他不逆置了,他直接输出for (int i = 0; i < n / K; ++i) {//枚举完整的n/K块for (int j = (i + 1) * K - 1; j > i * K; --j) {printf("%05d %d %05d\n", node[j].address, node[j].data, node[j - 1].address);}//下面是每一块的最后一个结点的next地址的处理printf("%05d %d ", node[i * K].address, node[i * K].data);if (i < n / K - 1) {	//如果不是最后一块.就指向下一块的最后一个结点printf("%05d\n", node[(i + 2) * K - 1].address);}else {	//是最后一块时if (n % K == 0)	printf("-1\n");else {printf("%05d\n", node[(i + 1) * K].address);for (int i = n / K * K; i < n; ++i) {printf("%05d %d ", node[i].address, node[i].data);if (i < n - 1) {printf("%05d\n", node[i + 1].address);}else {printf("-1\n");}}}}}return 0;
}

柳神的代码:

PS:我以为我三个数组就有点过分了,柳神直接全部都上了数组.还是我柳神强

还有那个逆置代码,是真的秀到了.

建议大家也记下来.

#include <iostream>
using namespace std;
int main() {int first, k, n, sum = 0;cin >> first >> n >> k;int temp, data[100005], next[100005], list[100005], result[100005];for (int i = 0; i < n; i++) {cin >> temp;cin >> data[temp] >> next[temp];}while (first != -1) {       //柳神的这个list就是用来存储排序好的地址的.list 0 就是一开始的地址//因为数据一直存放在data里面,所以data里面的东西一直都是可以不用改的list[sum++] = first;    first = next[first];}//result i 里面存放的也是list里面的数,result才是最后的结果.list也是一个备胎for (int i = 0; i < sum; i++) result[i] = list[i];//逆置的代码   for (int i = 0; i < (sum - sum % k); i++)//i / k * k + k - 1 - i % k 这个代码,我是想不出来的.有点秀的.result[i] = list[i / k * k + k - 1 - i % k];for (int i = 0; i < sum - 1; i++)printf("%05d %d %05d\n", result[i], data[result[i]], result[i + 1]);printf("%05d %d -1", result[sum - 1], data[result[sum - 1]]);return 0;
}

如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗

相信我，你也能变成光.

如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.