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 (≤) which is the total number of nodes, and a positive K (≤) 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>
#include <stdlib.h>
#define Null -1
#define MAXSIZE 100000
typedef int ElemType;
typedef int Ptr;
struct LISTNODE {
ElemType key;
int next;
}list[MAXSIZE];
int GetLength(Ptr start) {
int count = 0;
Ptr next = start;
while (next != Null) {
count++;
next = list[next].next;
}
return count;
}
//返回新的起始地址
int Reverse(Ptr p, int k) {
int count = 0;
Ptr cur, next, tmp;
cur = p;
next = list[cur].next;
for (int i = 0; i < k - 1; ++i) {
tmp = list[next].next;
list[next].next = cur;
cur = next;
next = tmp;
}
list[p].next = next;
return cur;
}
int ReverseWholeList(int firstPos, int len, int k)
{
if (len >= k) {
int startPos;//记录开始反转的第一个位置
int lastPos;//记录上次反转后的最后一个位置
//第一次反转
startPos = firstPos;
firstPos = Reverse(startPos, k);
lastPos = startPos;//反转后第一个位置变为最后一个位置
startPos = list[startPos].next;//反转后，第一个位置变为反转序列最后一个位置，取下个起始位置
//第二次到最后一次反转
for (int i = 1; i < len / k; ++i)
{
list[lastPos].next = Reverse(startPos, k);
lastPos = startPos;
startPos = list[startPos].next;
}
}
return firstPos;
}
void Print(Ptr firstPos) {
Ptr next = firstPos;
if(next == -1){
return;
}
while (list[next].next != Null) {
printf("%05d %d %05d\n", next, list[next].key, list[next].next);
next = list[next].next;
}
printf("%05d %d %d\n", next, list[next].key, list[next].next);
}
int main() {
int firstPos;
int N;
int k;
scanf("%d %d %d", &firstPos, &N, &k);
int addr, data, next;
for (int i = 0; i < N; ++i) {
scanf("%d %d %d", &addr, &data, &next);
list[addr].key = data;
list[addr].next = next;
}
int len = GetLength(firstPos);
firstPos = ReverseWholeList(firstPos, len, k);
Print(firstPos);
return 0;
}
结果：