【PAT (Basic Level) Practice】——【链表处理】1025 反转链表

【PAT (Basic Level) Practice】——【链表处理】1025 反转链表

文章目录

一【题目难度】二【题目编号】三【题目描述】四【题目示例】五【解题思路】六【最终得分】七【代码实现】八【提交结果】

一【题目难度】

乙级 二【题目编号】

1025 反转链表 (25 分) 三【题目描述】

给定一个常数 K K K 以及一个单链表 L L L，请编写程序将 L L L 中每 K K K 个结点反转。例如：给定 L L L 为 1→2→3→4→5→6， K K K 为 3，则输出应该为 3→2→1→6→5→4；如果 K K K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K K K 个元素不反转。 四【题目示例】

输入格式：
每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N ( ≤ 1 0 5 ) N (≤10^5 ) N(≤105)、以及正整数 K ( ≤ N ) K (≤N) K(≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。接下来有 N N N 行，每行格式为：
Address Data Next
其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

输出格式：
对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

输入样例：
00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：
00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

五【解题思路】

这个题如果给定一个普通链表肯定就是简单题了，但是难点就在于链表的初始化和边界条件的处理，我们首先定义结构体存储每个结点的数据，然后定义一个数组，依次存储每个结点，下面是关键步骤：
①：首先肯定是找到头结点，并且有效结点数加1（因为题目给的某个结点可能不在链上），然后将头结点交换到第一个位置
②：后面按照①都要交换，这就是链表的初始化，按照正常链表的格式存储在数组中，并且统计有效结点的个数
③：这一步非常重要，我们要按照k个一组逆置链表，可是我们已经将结点存储到数组中了，所以只需要按照数组的方式交换逆置结点即可，注意这里如果有剩余元素（不到k个结点，也就成不了一组），就不需要交换
④：然后按序输出即可，注意最后一个元素的Next为-1，并且输出格式需要注意，地址都是按照%05d输出，目的是五位数字对齐，和题目要求保持一致 六【最终得分】

25分 七【代码实现】

#include

struct Node
{
    int Address;
    int Data;
    int Next;
}node[100010];

int main()
{
    int begin,n,k,count = 0,end;
    struct Node temp;
    scanf("%d %d %d",&begin,&n,&k);
    for(int i = 0;i 
八【提交结果】 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5714762.html