[数据结构与算法]PAT 1025 反转链表 (25 分)C++

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

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数?N?(≤105)、以及正整数?K?(≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用??1?表示。

接下来有?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

根据视频将该部分解答后，重新分析，对于temp的使用以及链表的知识掌握具有深刻的意义。

设定一个二维数组，分别表示数据和下一地址，

定义两个变量l_address和f_address在开始第一轮循环之前或者刚开始都为100000；

开始循环后，在内部循环中l_address主要的作用是每次经过一轮循环等于此时的temp数值，temp数值在每次内循环中为指向的地址；

外部循环中f_address的作用是每次外循环，改变temp的数值，是两块之间的指针指向为反转之后的连接；同时也需要改变反转之后的l_address每次的起始位置；

最终输出数值中需要注意的一个点：

数据地址为五个数值，小于五位数的数据，空位用0填充，该部分，我们使用C语言中的cstdio头文件%05d设置。

完整参考代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
int num[100001][2];
int main(){
	int address,n,k;
	int data,next;
	cin>>address>>n>>k;
	num[100000][1]=address;
	for(int i=0;i<n;i++)
	{
		cin>>address>>data>>next;
		num[address][0]=data;
		num[address][1]=next; 
	} 
	address=100000;
	n=0;
	while(num[address][1]!=-1)
	{
		address=num[address][1];
		n++;
	}
	int l_address=100000;
	for(int i=0;i<n/k;i++)
	{
		int f_address=l_address;
		address=num[f_address][1];
		for(int j=0;j<k;j++)
		{
			int temp=address;
			address=num[address][1];
			num[temp][1]=l_address;
			l_address=temp;
		}
		int temp=num[f_address][1];
		num[temp][1]=address;
		num[f_address][1]=l_address;
		l_address=temp;
	} 
	address=num[100000][1];
	while(num[address][1]!=-1)
	{
		printf("%05d %d %05d\n",address,num[address][0],num[address][1]);
		address=num[address][1];
	}
	printf("%05d %d %d\n",address,num[address][0],num[address][1]);
	return 0;
} 

参考视频链接如下

PTA 乙题训练_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1Wi4y1V7Tc?p=25