PAT 1074 Reversing Linked List[链表][一般]
1074 Reversing Linked List (25)(25 分)
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.
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
题目大意:给出一个链表,按照数k对其进行反转,并输出反转后的链表。
代码来自:https://www.liuchuo.net/archives/1910
#include <iostream> #include<stdio.h> 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[sum++] = first; first = next[first]; } for (int i = 0; i < sum; i++) result[i] = list[i];//现在result里都已经是顺序排列了 for (int i = 0; i < (sum - sum % k); i++){ result[i] = list[i / k * k + k - 1 - i % k]; //printf("%d %d\n",i,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; }
//并没有真正的使用结构体来构造链表。data也是使用地址下标来存储,十分简洁。
1.由于输入的节点可能存在异常的,所以又重新统计了一下。
2.但是那个result被反转赋值为list的下标公式可真难。
这个代码来自:
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<iostream> #include<algorithm> using namespace std; int list[100010]; int node[100010][2]; int main() { int st,num,r; cin>>st>>num>>r; int address,data,next,i; for(i=0;i<num;i++) { cin>>address>>data>>next; node[address][0]=data; node[address][1]=next; } int m=0,n=st; while(n!=-1) { list[m++]=n; n=node[n][1]; } i=0; while(i+r<=m) { reverse(list+i,list+i+r); i=i+r; } for (i = 0; i < m-1; i++) { printf("%05d %d %05d\n", list[i], node[list[i]][0], list[i+1]); } printf("%05d %d -1\n", list[i], node[list[i]][0]); }
//这个和上边的思想类似,都是使用数组来存储。
1.data是通过二维数组中的第一维来表示,(其实都一样),均是通过地址下标找到的。
2.使用了reverse函数,没想到可以用reverse函数,队医一维数组来说。
while(i+r<=m) { reverse(list+i,list+i+r); i=i+r; }
//厉害。
相关文章
- java 字符串转集合_字符串转化为 List 集合
- jsonArray转list<map>
- c语言list的使用方法,c语言list操作
- BeanUtils如何优雅的拷贝List[通俗易懂]
- java list 转json 字符串_JSON的String字符串与Java的List列表对象的相互转换
- list,tensor,numpy相互转化
- 【Redis 系列】redis 学习三,redis 数据结构之 string 和 list 基本使用及熟悉
- 【Linux 内核 内存管理】RCU 机制 ④ ( RCU 模式下更新链表项 list_replace_rcu 函数 | 链表操作时使用 smp_wmb() 函数保证代码执行顺序 )
- 【Kotlin】集合操作 ③ ( List 集合遍历 | for in | forEach | forEachIndexed | List 通过解构一次性给多个元素赋值 )
- ORA-32484: duplicate name found in cycle column list for CYCLE clause of WITH clause ORACLE 报错 故障修复 远程处理
- ORA-02774: Invalid request list latch time out value ORACLE 报错 故障修复 远程处理
- list java中List对象通用排序算法详解编程语言
- java中对List中对象排序实现详解编程语言
- Linux内核之旅:探索列表及其功能(linux内核list)
- C++ list,STL list(双向链表)详解
- Hibernate Criteria接口 list方法:返回一个List集合
- 利用Redis实现List元素的排序(redis排序list)
- 利用Redis构建新的List存储方式(redis存储list)
- 中一部分元素用Redis快速获取List元素(redis获取list)
- Managing Your User List with MySQL: A Comprehensive Guide(mysql用户列表)
- Mastering List Operations in Redis: Tips and Tricks for Optimal Performance(redis操作list)
- 的优势玩转Redis:List缓存的有点优势(redis 缓存list)
- Oracle中使用List命令查看表结构(list命令oracle)
- 实现使用List实现Redis队列(redis队列用list)
- Redis实现高效的List读取(redis读list)