题目地址
https://pta.patest.cn/pta/test/16/exam/4/question/664
5-2 Reversing Linked List (25分)
Given a constant KK and a singly linked list LL, you are supposed to reverse the links of every KK elements on LL. For example, given LL being 1→2→3→4→5→6, if K = 3K=3, then you must output 3→2→1→6→5→4; if K = 4K=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 NN (le 10^5≤105) which is the total number of nodes, and a positive KK (le N≤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 NN 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
/*
评测结果
时间 结果 得分 题目 编译器 用时（ms） 内存（MB） 用户
2017-07-08 15:54 答案正确 25 5-2 gcc 131 3
测试点结果
测试点 结果 得分/满分 用时（ms） 内存（MB）
测试点1 答案正确 12/12 2 1
测试点2 答案正确 3/3 14 1
测试点3 答案正确 2/2 1 1
测试点4 答案正确 2/2 2 1
测试点5 答案正确 2/2 2 1
测试点6 答案正确 3/3 131 3
测试点7 答案正确 1/1 2 1
*/
#include<stdio.h>
#define MAXLEN 100002
struct node {
int data;
int next;
};
int k,head;
struct node workArray [MAXLEN];
int Input(struct node array[])
{
int i,inputHead,inputLength;
int index,data,next;
scanf("%d %d %d",&inputHead,&inputLength,&k);
for (i=0;i<inputLength;i++){
scanf("%d %d %d",&index,&data,&next);
array[index].data=data;
array[index].next=next;
}
return inputHead;
}
int count(int head,struct node array[])
{
int i,cnt=1;
i=head;
while(array[i].next!=-1){
cnt++;
i=array[i].next;
}
return cnt;
}
void PrintList(int head,struct node array[])
{
int idx=head;
while(array[idx].next!= -1){
printf("%05d %d %05d
",idx,array[idx].data,array[idx].next);
idx=array[idx].next;
}
printf("%05d %d %d",idx,array[idx].data,array[idx].next);
}
int ReverseList(struct node array[],int *head,int k)
{
/*
首先用count求链表长度，放到cnt中保存。每次执行cnt自身减掉k，如果cnt<k则不进行翻转
然后使用ptr1 ptr2 ptr3 三个指针
ptr1为当前节点 ptr2为下一个节点 将ptr1->ptr2改为ptr2->ptr1。因为ptr2中的next原有内容会丢失，故用ptr3保存ptr2的下一个节点
执行完一次后，k个节点区间内，头尾互换。
故lastend保存前一区块的末端，是上一区间的头节点
nexthead即下一区块的头结点，同样也是该区块翻转完后的末端。于是提前用lastend=nexthead保存。
*/
int cnt;
if(k==1)
return;
cnt=count(*head,array);
int i,ptr1,ptr2,ptr3,firstflag=0,nexthead=*head,lastend=-2;//ptr1指当前指针，ptr2指下一个要指向ptr1的，ptr3指向还未做反转的下一个。
while(cnt>=k){
// printf("-------head=%d,nexthead=%d,cnt=%d
",*head,nexthead,cnt);//for_test
ptr1=nexthead;
ptr2=array[ptr1].next;
for(i=1;i<k;i++){
ptr3=array[ptr2].next;
array[ptr2].next=ptr1;
ptr1=ptr2;
ptr2=ptr3;
}
array[nexthead].next=ptr3;//主要反转做完后，重新定义头尾节点的指向。
if(firstflag==0){
lastend=nexthead;
*head=ptr1;//因为在循环中最后改变了ptr2的值，所以此处用ptr1 。
}
else{
array[lastend].next=ptr1;
lastend=nexthead;
}
firstflag++;
nexthead=ptr2;
cnt-=k;
}
}
int main()
{
head=Input(workArray);
ReverseList(workArray,&head,k);
PrintList(head,workArray);
}