题目链接：1025 反转链表

思路：

这题之前因为没有AC所以跳过了，现在回来补坑～ 

数据结构部分： 很明显这题需要空间换时间的思路，使用数组快速随机访问，我是采用结构体数组保存的，我看其他大神也有用3个数组分别保存数据的，可能操作起来更加方便吧。个人觉得用结构体会让数据更加一体化便于管理，实现起来更加直观一些。结构体内容：数据域data、指针域next均为int型。按照题目要求数据量小于，因为我后面要使用头插法需要头节点，故我设置了一个100001大小的数组。数据输入： 输入结点时先识别输入到哪个地址。再输入该地址的数据和next指针。将用不到的10000设为头节点，链接到题目的首结点前。因为数据中可能会有不在链表内的结点，输入后从头遍历一遍链表，修正结点数N的值。本题核心——分段倒序： 需要倒序的片段共有N/K段，K为1无需倒序。从每段的第二个结点开始使用使用头插法，该方法需要有3个指针，头节点，当前结点的前驱，当前结点，每个结点插入完成后，前驱与头节点位置不变，当前结点变为前驱结点的下一个。每段结束后，头节点改为前驱结点，前驱结点后移一位。直至完成N/K轮。输出 格式化我觉得printf还是比cout配合<iomanip>好写一些。固定位数补0即"%0nd"。注意-1地址不用格式化，直接输出-1。

问题解决～话说每次看到大佬用了自己一半的行数就写完了内心就有种淡淡的忧伤～

#include <iostream> using namespace std; struct Node{ int data; int next; }node[100001];//静态链表，100000作头节点 int main(){ int L,N,K,ad; cin >> L >> N >> K; //逐个输入结点信息 for(int i=0;i<N;i++){ cin >> ad; cin >> node[ad].data >> node[ad].next; } node[100000].next = L; //更正结点数量 N = 1; while(node[L].next>-1){ N++; L = node[L].next; } //倒序轮次N/K，每次从第二个开始倒 int p = 100000 ,q, r = node[100000].next; for(int i=0;i<N/K && K!=1;i++){ for(int j=0;j<K-1;j++){ q = node[r].next; node[r].next = node[q].next; node[q].next = node[p].next; node[p].next = q; q = node[r].next; } p = r; r = node[p].next; } L = node[100000].next; //按照格式要求输出链表 for(int i=0;i<N;i++){ if(node[L].next != -1)printf("%05d %d %05d\n",L,node[L].data,node[L].next); else{ printf("%05d %d -1\n",L,node[L].data); break; } L = node[L].next; } return 0; }