02-线性结构3 Reversing Linked List (25分)

PS：在网上看了看关于这道题的许多解析，觉得还是这种数组法最容易理解。主要是我觉得这道题的输入方式使得构造链表的操作不好表述。 首先可以看到一个规律是:Address与Data是绑定的，是不可变的，改变的是Next，于是借助这个关系，创建三个大容量数组data next list 其中第一个负责在输入的Address下标下记录data next数组同理 而list数组负责顺着地址将数据串成顺序形式，也就是说，实际上此数组占用了，在接下来的操作中，只需要操纵list数组的位置就好。 而读题意，是在K个节点的区间内翻转，所以翻转操作的第一个循环，就是限制在K个节点内操作，而第二个循环，则是使用一个翻转数组的经典操作，可以记住此段方便使用 最后注意格式输出

具体代码实现

#include <stdio.h> #define MAX_SIZE 100005 int main() { int data[MAX_SIZE]; int next[MAX_SIZE]; int list[MAX_SIZE]; int firstAdd,N,K,i,j; scanf("%d %d %d",&firstAdd,&N,&K); for(i=0;i<N;i++){ int tempAdd,tempData,tempNext; scanf("%d %d %d",&tempAdd,&tempData,&tempNext); data[tempAdd] = tempData; next[tempAdd] = tempNext; } int sum = 0; while(firstAdd != -1){ //通过list数组，记录顺延的地址 list[sum++] = firstAdd; firstAdd = next[firstAdd]; } for(i=0;i<sum-sum%K;i+=K){ //K个节点时一个翻转区间 for(j=0; j<K/2 ;j++){ //反转这个区间内的链表 int t = list[i+j]; list[i+j] = list[i+K-j-1]; list[i+K-j-1] = t; //翻转数组经典操作 } } for(i=0;i<sum-1;i++){ printf("d %d d\n",list[i],data[list[i]],list[i+1]); } printf("d %d -1\n",list[sum-1],data[list[sum-1]]); return 0; }