本文由参考于柳神博客写成
柳神的博客,这个可以搜索文章
柳神的个人博客,这个没有广告,但是不能搜索
还有就是非常非常有用的 算法笔记 全名是
算法笔记 上级训练实战指南 //这本都是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.
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 Nextwhere Address is the position of the node, Data is an integer, and Next is the position of the next node.
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.
给你一个链表,然后让你反转这个链表
Address Data Next格式是这样的.
最后结束的链表的地址是 -1
① 我们可以用静态做-动态难,还麻烦.
node[1000000]的结构体
② 我的想法,就是把地址和数据绑定在一起.
然后输入的地址就直接是node的下标
然后我这个人有点小傻
然后再创建一个node[100000] 的数组来存储我们排序好的数组
③ 然后再创建一个node[100000]的数组来存储我们打乱后的数据.
可能结果,你没有考虑到中间节点就断开的情况
例子如下:
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("d %d d\n", Fin[i].next, Fin[i].data,Fin[i+1].next); printf("d %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赋值给n n = 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("d %d d\n", node[j].address, node[j].data, node[j - 1].address); } //下面是每一块的最后一个结点的next地址的处理 printf("d %d ", node[i * K].address, node[i * K].data); if (i < n / K - 1) { //如果不是最后一块.就指向下一块的最后一个结点 printf("d\n", node[(i + 2) * K - 1].address); } else { //是最后一块时 if (n % K == 0) printf("-1\n"); else { printf("d\n", node[(i + 1) * K].address); for (int i = n / K * K; i < n; ++i) { printf("d %d ", node[i].address, node[i].data); if (i < n - 1) { printf("d\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("d %d d\n", result[i], data[result[i]], result[i + 1]); printf("d %d -1", result[sum - 1], data[result[sum - 1]]); return 0; }如果这篇文章对你有张帮助的话,可以用你高贵的小手给我点一个免费的赞吗
相信我，你也能变成光.
如果你有任何建议,或者是发现了我的错误,欢迎评论留言指出.
