P 1025 链表反转
转跳点：
给定一个常数 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，即最后不到 K 个元素不反转。
输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤)、以及正整数 K (≤)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 − 表示。
接下来有 N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。
输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。
输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1
1 for (int i = 0; i < Quotient; i++)
2 {
3 for (int j = 0; j < K / 2; j++)
4 {//因为不是和冒泡那样的连续赋值而是交换所以只要一般的的次数
5
6 //交换
7 ListNode temp = List[K * i + j];
8 List[K * i + j] = List[K * (i + 1) - j - 1];
9 List[K * (i + 1) - j - 1] = temp;
10 }
11 }
为什么交换次数是K/2，举个栗子：1 2 3 4 5，要逆序，最暴力的方法就是从第一个数开始一个个往后移动，这无疑浪费了大量的时间在交换上，认真观察会发现，其实交换将1 和 5交换 2 和 4 就可以达到效果。奇数的时候就是中间位不用动，偶数的时候刚好对半分。所以不分奇偶。
大佬们可以跳过下面这一段（写一个小姐姐看的）被划掉了，看不见看不见。
那为什么是k*I+J和K * (i + 1) - j - 1交换，将I去掉后，不难发现就是将数组第一位和第K位交换，数组第二位和第K-1位上的数交换，以此类推*I是因为这是第I组刚好也相当于下标
i = 0的时候
0 和 k-1 换，
1 和 k-2 换，
……
k/2-1 和 k/2+1
i = 2时
k 和 2k-1 换，
k+1 和 2k-2 换，
……
2k/2-1 和 2k/2+1
……
i = n 时
nk 和 2k-1 换，
nk+1 和 nk-2 换，
……
nk/2-1 和 nk/2+1
最后就是代码了：
1 #include <stdio.h>
2 #include <stdlib.h>
3 #define MAXSIZE 100011
4 typedef struct
5 {
6 int Address;
7 int Data;
8 int Next;
9 } ListNode;
10
11 int main(void)
12 {
13 int head, n, K;
14 ListNode List[MAXSIZE];
15 scanf("%d%d%d", &head, &n, &K);
16
17 for (int i = 0; i < n; i++)
18 {
19 scanf("%d %d %d", &List[i].Address, &List[i].Data, &List[i].Next);
20 }
21
22 //线找到首地址
23 for (int i = 0; i < n; i++)
24 {
25 if (List[i].Address == head)
26 {
27 ListNode temp = List[i];
28 List[i] = List[0];
29 List[0] = temp;
30 break;
31 }
32 }
33
34 //整理链表顺序
35 for (int i = 0; i < n; i++)
36 {
37 if (-1 == List[i].Next)
38 {
39 n = i + 1;
40 break;
41 }
42 for (int j = i + 1; j < n; j++)
43 {
44 if (List[j].Address == List[i].Next)
45 {
46 ListNode temp = List[i + 1];
47 List[i + 1] = List[j];
48 List[j] = temp;
49 break;
50 }
51 }
52 }
53
54 //取出需要交换的次数
55 int Quotient = n / K;
56
57 for (int i = 0; i < Quotient; i++)
58 {
59 for (int j = 0; j < K / 2; j++)
60 {//因为不是和冒泡那样的连续赋值而是交换所以只要一般的的次数
61
62 //交换
63 ListNode temp = List[K * i + j];
64 List[K * i + j] = List[K * (i + 1) - j - 1];
65 List[K * (i + 1) - j - 1] = temp;
66 }
67 }
68
69 //重写地址
70 for (int i = 0; i < Quotient * K; i++)
71 {
72 List[i].Next = List[i + 1].Address;
73 }
74 List[n - 1].Next = -1;
75
76
77 for (int i = 0; i < n; i++)
78 {
79 if (-1 == List[i].Next)
80 {//特殊处理-1;
81 printf("%05d %d %d\n", List[i].Address, List[i].Data, List[i].Next);
82 continue;
83 }
84 printf("%05d %d %05d\n", List[i].Address, List[i].Data, List[i].Next);
85 }
86
87 return 0;
88 }
这几组是我自己的测试数据可以拿去试试（还有一组丢了，有无效数据不能整除的）这几组数据过了之后，应该就能A了
有无效数据 能整除 不能整除
PTA不易，诸君共勉！
最新文章
- javascript语句——表达式语句、块语句、空语句和声明语句
- ural 1073. Square Country
- ListCell Animation in ListView
- [AngularJS] angular-formly: Default Options
- ubuntu开机黑屏
- VMWare、KVM、Virtualbox克隆或复制Linux虚拟机后eth0找不到的解决方案
- 复旦高等代数 I（18级）每周一题
- 用户id，组id和文件访问权限
- Spring，SpringMvc配置常见的坑，注解的使用注意事项，applicationContext.xml和spring.mvc.xml配置注意事项，spring中的事务失效，事务不回滚原因
- learning makefile manner of working
- nginx-1.12.0版本（编译安装）-自定义安装路径
- linux环境下 卸载 Oracle11G
- ELK篇---------elasticsearch集群安装配置
- hdu 4998 矩阵表示旋转
- caffe windows编译
- Shell替换：Shell变量替换，命令替换，转义字符
- 手机QQ会员H5加速方案——sonic技术内幕
- aspnetcore 认证相关类简要说明二
- KVM虚拟机无法启动
- 汉诺塔问题java实现