PAT 1025.反转链表

还是学习了小姐姐的方法

首先输入的方法是

本地址  data值  下一个地址

建一个data数组，一个next数组，一个List数组

存储方式按本地址存 如：data[此地址]，next[此地址]

for(int i=0;i<n;i++)
{int temp;cin >> temp;//当前地址 
 cin >> data[temp] >> next[temp];	
}	

List目的是为了按顺序存储链表的地址，sum表示有效的点

int sum=0;//list表用来按顺序存地址 
while(first!=-1) 
{list[sum++] = first;//存地址 first = next[first];
}

头文件algorithm中有reverse函数，可以倒置

for(int i=0;i<sum-sum%m;i = i+m)
{reverse(list+i,list+i+m);
}

最后打印

List[i]   data[list[i]]   list[i+1]

完整代码

#include<iostream>
#include<stdio.h>
#include<algorithm>
using namespace std;int main()
{int first,n,m;cin >> first >> n >> m;int data[100005],next[100005],list[100005];for(int i=0;i<n;i++){int temp;cin >> temp;//当前地址 cin >> data[temp] >> next[temp];	}	int sum=0;//list表用来按顺序存地址 while(first!=-1) {list[sum++] = first;//存地址 first = next[first];}for(int i=0;i<sum-sum%m;i = i+m){reverse(list+i,list+i+m);}for(int i=0;i<sum-1;i++){printf("%05d %d %05d\n",list[i],data[list[i]],list[i+1]);} printf("%05d %d -1", list[sum - 1], data[list[sum - 1]]);return 0; 
}