题目

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K=3, then you must output 3→2→1→6→5→4; if K=4, you must output 4→3→2→1→5→6.

Input Specification:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (≤10​5​​) which is the total number of nodes, and a positive K (≤N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output Specification:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

Sample Input:

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

Sample Output:

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

解题思路

　　题目大意： 给N个链表结点，以及K，对每K个长度的链表做逆置，输出逆置后的链表。
　　解题思路： 题目并不难理解，但是一些细节要注意——
　　1. 首先还是先创建链表，因为并不是每个结点都在链表上，先筛选出在链表上的结点，输入使用一个数组，运用哈希的思想，以空间换时间，不然会超时；
　　2. 然后做逆置，注意是每K个链表结点翻转，可能会翻转多次；
　　3. 最后注意边界情况，可能有一个结点的情况；

/*
** @Brief:No.1073 of PAT advanced level.
** @Author:Jason.Lee
** @Date:2019-01-23
** @Solution: Accepted!
*/
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct node{
	int addr;
	int data;
	int next;	
};

node nlist[100000];

int main(){
	int K,N,first;
	while(scanf("%d%d%d",&first,&N,&K)!=EOF){
		node input{-1,0,-1};
		fill(nlist,nlist+100000,input);
		vector<node> vn;
		for(int i = 0;i<N;i++){
			scanf("%d%d%d",&input.addr,&input.data,&input.next);
			nlist[input.addr] = input;
		}
		int next = first;
		while(next!=-1&&nlist[next].addr!=-1){
			vn.push_back(nlist[next]);
			next = nlist[next].next;
		}
		int index = 0;
		while(index+K<=vn.size()){
			reverse(begin(vn[index]),begin(vn[index+K]));
			index+=K;
		}
		printf("%05d %d ",vn[0].addr,vn[0].data);
		for(int i=1;i<vn.size();i++){
			printf("%05d\n%05d %d ",vn[i].addr,vn[i].addr,vn[i].data);
		}
		printf("-1\n");
	}
	return 0;
}

总结

　　这道题和PAT乙级1025是一模一样的题目，只是变成了英文版，没什么难的。