1074. Reversing Linked List (25)

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⁵) 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.

00100 6 400000 4 9999900100 1 1230968237 6 -133218 3 0000099999 5 6823712309 2 33218Sample Output:
00000 4 3321833218 3 1230912309 2 0010000100 1 9999999999 5 6823768237 6 -1
可以直接转置地址
#include<cstdio>#include<algorithm>using namespace std;const int maxn = 1e5 + 10;int value[maxn], nt[maxn];  //存放值的数组   下一地址数组 int op[maxn];               //操作数组 int main(){	int head, n, k, address;	scanf("%d %d %d", &head , &n, &k);	for(int i = 0; i < n; ++i){		scanf("%d", &address);		scanf("%d %d", &value[address], &nt[address]);	}	int total = 0;	for(int i = head; i != -1; i = nt[i]){		op[total++] = i;	}	for(int i = 0; i + k <= total; i +=k){		for(int low = i, high = low + k - 1; low < high; ++low, --high){			swap(op[low], op[high]);		}	}	for(int i = 0; i < total; ++i){		if(i != total - 1){			printf("%05d %d %05d/n", op[i], value[op[i]], op[i + 1]);		}else{			printf("%05d %d -1/n", op[i], value[op[i]]);		}	}	return 0;}