02-线性结构3 Reversing Linked List (25分)
List 结构 25 02 线性 Linked
2023-09-14 08:57:14 时间
02-线性结构3 Reversing Linked List (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 (≤) which is the total number of nodes, and a positive K (≤) 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
提交代码:
#include <stdio.h> #include <stdlib.h> #define Null -1 #define MAXSIZE 100000 typedef int ElemType; typedef int Ptr; struct LISTNODE { ElemType key; int next; }list[MAXSIZE]; int GetLength(Ptr start) { int count = 0; Ptr next = start; while (next != Null) { count++; next = list[next].next; } return count; } //返回新的起始地址 int Reverse(Ptr p, int k) { int count = 0; Ptr cur, next, tmp; cur = p; next = list[cur].next; for (int i = 0; i < k - 1; ++i) { tmp = list[next].next; list[next].next = cur; cur = next; next = tmp; } list[p].next = next; return cur; } int ReverseWholeList(int firstPos, int len, int k) { if (len >= k) { int startPos;//记录开始反转的第一个位置 int lastPos;//记录上次反转后的最后一个位置 //第一次反转 startPos = firstPos; firstPos = Reverse(startPos, k); lastPos = startPos;//反转后第一个位置变为最后一个位置 startPos = list[startPos].next;//反转后,第一个位置变为反转序列最后一个位置,取下个起始位置 //第二次到最后一次反转 for (int i = 1; i < len / k; ++i) { list[lastPos].next = Reverse(startPos, k); lastPos = startPos; startPos = list[startPos].next; } } return firstPos; } void Print(Ptr firstPos) { Ptr next = firstPos; if(next == -1){ return; } while (list[next].next != Null) { printf("%05d %d %05d\n", next, list[next].key, list[next].next); next = list[next].next; } printf("%05d %d %d\n", next, list[next].key, list[next].next); } int main() { int firstPos; int N; int k; scanf("%d %d %d", &firstPos, &N, &k); int addr, data, next; for (int i = 0; i < N; ++i) { scanf("%d %d %d", &addr, &data, &next); list[addr].key = data; list[addr].next = next; } int len = GetLength(firstPos); firstPos = ReverseWholeList(firstPos, len, k); Print(firstPos); return 0; }
结果:
相关文章
- 利用HashSet给list去重[通俗易懂]
- java List去除重复数据的五种方式
- jsonArray转list<map>
- 【说站】java数组转list
- 数组使用arrays.aslist转化为集合_int数组转list集合
- ORA-28166: duplicate rolename in list ORACLE 报错 故障修复 远程处理
- ORA-30191: missing argument list ORACLE 报错 故障修复 远程处理
- redis用list做消息队列的实现示例
- SpingMVC实现集合参数(Could not instantiate bean class [java.util.List])详解编程语言
- Redis List 操作简明教程(redislist操作)
- 创建list ALV tree[RS_TREE_LIST_DISPLAY]详解编程语言
- C++ list(STL list)排序及合并元素方法详解
- List头文件助力Linux内核开发(list.hlinux)
- Linux命令:学会使用List命令管理目录列表(linuxlist命令)
- 的优势玩转Redis:List缓存的有点优势(redis 缓存list)
- 利用Redis List对象提升系统性能(redis list对象)
- Oracle数据库操作利用入参List实现批量处理(oracle入参list)
- 监测redis List动态稳定性突破极限(监听redis list)
- 使用Redis实现List存储(向redis中存list)
- Redis实现分页列表存储技术简介(分页list存redis)
- 从Redis读取List数据简单又高效(从redis读取list)
- Redis中List与Set的应用(redis集合与list)
- 实现使用List实现Redis队列(redis队列用list)
- 警惕Redis List被空出(redis里list为空)
- 集合类List与Dictonary实例练习
- JSMap和List的简单实现代码
- 将DataTable转换成List<T>实现思路及示例代码