原题链接：http://www.patest.cn/contests/mooc-ds/02-%E7%BA%BF%E6%80%A7%E7%BB%93%E6%9E%841

02-线性结构1. Reversing Linked List (25)

时间限制 400 ms

内存限制 65536 kB

代码长度限制 8000 B

判题程序 Standard 作者 CHEN, Yue

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 (<= 105) 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      

#include <stdio.h>
#define MAX 100000
typedef struct{
	int data;
	int next;
}Node;
int CountNodes(Node* list, int pList) {	//计算并返回单链表节点数
	int cnt = 1;
	while((pList = list[pList].next) != -1)
		cnt++;
	return cnt;
}
int ReverseK(Node* list, int pList, int n, int k) {
	int prevNode, currNode, nextNode;	//需要连接的前一个节点、当前节点、后一个节点
	prevNode = -1;
	currNode = pList;
	nextNode = list[currNode].next;
	int lastHead, head = -1;
	for(int i = 0; i < n / k; i++){	//分为n/k段分别逆转，每段k个节点
		lastHead = head;			//记录前一段的（未逆转的）头结点，以便连接到当前段的(未逆转的）尾节点
		head = currNode;			//记录当前段的头结点
		for(int j = 0; j < k; j++) {	//k个节点逆转：后一个节点指向前一个节点
			list[currNode].next = prevNode;
			prevNode = currNode;
			currNode = nextNode;
			nextNode = list[nextNode].next;
		}
		if(i == 0)			//第一段逆转后的头结点将作为表头返回
			pList = prevNode;
		else				//连接逆转后的前后两段
			list[lastHead].next = prevNode;
	}
	list[head].next = currNode;		//将不用逆转的剩余部分连接到逆转链表尾部
	return pList;
}
void printList(Node* list, int p) {
	while(list[p].next != -1){
		printf("%05d %d %05d\n", p, list[p].data, list[p].next);
		p = list[p].next;
	}
	printf("%05d %d %d\n", p, list[p].data, list[p].next);
}
int main() {
	int pList, n, k;
	scanf("%d%d%d", &pList, &n, &k);
	Node list[MAX];
	int addr, data, next;
	for(int i = 0; i < n; i++){
		scanf("%d%d%d", &addr, &data, &next);
		list[addr].data = data;
		list[addr].next = next;
	}
	int num = CountNodes(list, pList);	//因输入中有无效的节点，需要先计算单链表中的总结点数
	int pNewList = ReverseK(list, pList, num, k);
	printList(list, pNewList);

	return 0;
}