题目粗心:
现有一个长度为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;}