共计 2223 个字符，预计需要花费 6 分钟才能阅读完成。
题目粗心:
现有一个长度为 N, 终点为 begin_address 的单链表, 要求每 K 个结点进行逆置, 最初不够 K 个结点的不必逆置, 要求输入最初逆置实现的单链表。
算法思路：
这里采纳模仿单链表逆置的办法，咱们应用 node 数组存储所有输出的节点，result存储最初逆置完结后的单链表。对于单链表的逆置应该想到头插法，于是咱们首先为 result 链表创立一个头结点，这里头结点的地址得保障肯定不在输出的链表之中，于是选取了 100004 作为头结点地址。而后计算该单链表有几组须要逆置的结点, 应用 group 变量保留，对于每一组, 咱们应用头插法插入到新建链表 result 中, 这样就实现了 K 个结点的逆置, 同时为了不便更新头结点的地位，咱们应用 tail 来标记 result 尾节点的地位，在第一次插入的时候更新为插入节点的地址。这样在每一组插入结束后就更新头结点地位为 tail，以此类推，待所有组的节点均插入到result 链表之中。最初判断是否还残余结点, 如果还有, 那么用尾插法插入到 result 链表中, 而后从头结点的下一个结点输入该新链表即可。
留神点：
1、对于 PAT 的题目有可能输出的数据有效, 尤其是单链表, 所有咱们得先遍历一遍链表, 统计链表无效结点个数 count(在输出单链表上的节点个数), 目标是为了计算逆置的组数group。
2、因为题目给的地址全是 5 位数字，输入也得保障是 5 位数，除了 - 1 例外。
3、判断是否还有残余插入结点的办法就是work_n 是否等于 -1, 因为等于 - 1 阐明所有组数的结点插入结束后就达到了空结点, 前面不可能再有结点
4、对于result 链表的取得，肯定得新建一个节点 p，而后更新 p 的数据再插入到 result 中，不要间接更新 result 的地址，比方 result[work_n].address = work_n, 因为result[work_n] 示意的是节点，节点都没有增加进链表中，如何记录地址信息呢？
5、能够应用建设 address 与data,address与 next 的映射关系，间接逆置 address，而后其 next 为上一个节点的address 来解决，然而并没有间接逆置单链表直观(容易想到)。
提交后果：
AC 代码：
#include <cstdio>
using namespace std;
struct Node{
int address;
int data;
int next;
}node[100005],result[100005];
int main(){
int begin_address,N,K;
scanf("%d %d %d",&begin_address,&N,&K);
Node n{};// 暂存输出的每一个节点
for (int i = 0; i < N; ++i) {scanf("%d %d %d",&n.address,&n.data,&n.next);
node[n.address] = n;
}
// 统计输出的链表中无效节点的个数
int count = 0;
int work_n = begin_address;// 工作在 node 链表上的指针
while (work_n!=-1){
++count;
work_n = node[work_n].next;
}
// 计算能够逆置的组数
int group = count/K;
// 创立 result 链表的头结点
Node head{100004,0,-1};
result[head.address] = head;
// 对于每一组的每个节点采纳头插法插入到 result 链表中去
work_n = begin_address;// 重置 work_n
int begin = head.address;// result 的头指针
int tail = -1;//result 的尾指针，指向最初一个节点
for (int i = 0; i < group; ++i) {for (int j = 0; j < K; ++j) {Node p{work_n, node[work_n].data, result[begin].next};
result[begin].next = p.address;
result[p.address] = p;
work_n = node[work_n].next;// 指向下一个节点地位
if(j==0){tail = p.address;// 更新尾节点的地址}
}
// 每一组节点逆置结束就更新头节点
begin = tail;
}
while (work_n!=-1){
// 前面还有一些无需逆置的节点, 采纳尾插法插入到链表中
Node p{work_n, node[work_n].data, -1};
result[begin].next = p.address;
result[p.address] = p;
begin = result[begin].next;// 指向 result 下一个节点地位
work_n = node[work_n].next;// 指向 node 下一个节点地位
}
for(begin = result[100004].next;begin!=-1;begin = result[begin].next){if(result[begin].next==-1){printf("%05d %d -1\n",result[begin].address,result[begin].data);
} else {printf("%05d %d %05d\n",result[begin].address,result[begin].data,result[begin].next);
}
}
return 0;
}
