【PAT (Basic Level) Practice】——【链表处理】1110 区块反转
文章目录
- 一【题目难度】
- 二【题目编号】
- 三【题目描述】
- 四【题目示例】
- 五【解题思路】
- 六【最终得分】
- 七【代码实现】
- 八【提交结果】
一【题目难度】
- 乙级
二【题目编号】
- 1110 区块反转 (25 分)
三【题目描述】
- 给定一个单链表 L L L,我们将每 K K K 个结点看成一个区块(链表最后若不足 K K K 个结点,也看成一个区块),请编写程序将 L L L 中所有区块的链接反转。例如:给定 L L L 为 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 1→2→3→4→5→6→7→8 1→2→3→4→5→6→7→8,K K K 为 3 3 3,则输出应该为 7 → 8 → 4 → 5 → 6 → 1 → 2 → 3 7→8→4→5→6→1→2→3 7→8→4→5→6→1→2→3。
四【题目示例】
-
输入格式:
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N(≤1 0 5 ) N (≤10^5 )N(≤105)、以及正整数 K(≤N) K (≤N)K(≤N),即区块的大小。结点的地址是 5 位非负整数,NULL 地址用 −1 表示。
接下来有 N NN 行,每行格式为:
Address Data Next
其中 Address 是结点地址,Data 是该结点保存的整数数据,Next 是下一结点的地址。 -
输出格式:
对每个测试用例,顺序输出反转后的链表,其上每个结点占一行,格式与输入相同。 -
输入样例:
00100 8 3
71120 7 88666
00000 4 99999
00100 1 12309
68237 6 71120
33218 3 00000
99999 5 68237
88666 8 -1
12309 2 33218 -
输出样例:
71120 7 88666
88666 8 00000
00000 4 99999
99999 5 68237
68237 6 00100
00100 1 12309
12309 2 33218
33218 3 -1
五【解题思路】
- 这道题目的思路比较清晰,就是扫描输入之后计算有多少块,然后按块逆置链表。但是测试样例6应该存在游离节点(不在链表之上的节点),所以需要重新计算链表长度,还需要把整个链表串联起来,输出的时候注意输出格式
六【最终得分】
- 25分
七【代码实现】
#includetypedef struct NODE{ int address; int data; int next;}node;int main(){ int begin,n,k,address,data,next,index = 0,block,len; node list[100000],res[100000]; scanf("%d %d %d",&begin,&n,&k); for(int i = 0;i<n;i++) { scanf("%d %d %d",&address,&data,&next); list[address].address = address; list[address].data = data; list[address].next = next; } while(1) { res[index++] = list[begin]; begin = list[begin].next; if(begin == -1) { break; } } len = index; block = (len + k - 1) / k; for(int i = 0;i<block;i++) { for(int j = 0;j<k && j+(block - i - 1) * k < len;j++) { if(i != 0 || j != 0) { printf("%05d\n",res[j+(block - i - 1) * k].address); } printf("%05d %d ",res[j+(block - i - 1) * k].address,res[j+(block - i - 1) * k].data); } } printf("-1"); return 0;}