1074 Reversing Linked List （25 point(s)）

题解

注意[i, i+ K)左闭右开。

C++ < algorithm > 中定义的reverse函数用于反转在[first,last)范围内的顺序

template <class BidirectionalIterator>
void reverse (BidirectionalIterator first,BidirectionalIterator last);

例如，交换vector容器中元素的顺序

vector<int> v={1,2,3,4,5};
reverse(v.begin(),v.end());//v的值为5，4，3，2，1

当然，你也可以通过它方便的反转string类的字符串

string str="C++REVERSE";
reverse(str.begin(),str.end());//str结果为ESREVER++C

测试数据：

00100 6 2
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
const int MAXN = 1e6 + 10;
using namespace std;
struct node {
	int data;
	int neaddr;
}link[MAXN];
int first, cnt, L, K, x;
vector<int> res;
int main() {
	scanf("%d%d%d", &first, &L, &K);
	for(int i = 0; i < L; ++i) {
		scanf("%d", &x);
		scanf("%d%d", &link[x].data, &link[x].neaddr);
	}
	while(first != -1) {
		res.push_back(first);
		first = link[first].neaddr;
	}
	for(int i = 0; i + K <= res.size(); i += K) reverse(res.begin() + i, res.begin() + i + K); // 注意[i, i + K) 
	for(int i = 0; i < res.size() - 1; ++i) printf("%05d %d %05d\n", res[i], link[res[i]].data, res[i + 1]);
	printf("%05d %d -1\n", res[res.size() - 1], link[res[res.size() - 1]].data);
	return 0;
}