1025 反转链表 (25 分)+测试点6
题目
给定一个常数 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 (≤10?5??)、以及正整数 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
解题思路
- 一行信息包含节点地址，数据以及下一结点地址，通过一个结构体才存放每一行信息。
- 通过阅读题目可以看出输入的信息是无序的，所以在进行反转链表操作之前，就是将输入的无序信息转化成有序信息。
- 有了以上思路，我们开始读数据，第一行通过三个变量获取首地址，结点数和步长，对于结点信息使用一个结构体数组进行读取，已经得到节点个数所以通过一个for循环读取每一行的数据，关于结点存储的的问题，最简单的是按顺序将每行信息存到数组中，但是带来的问题是，在对结点进行排序时，每次寻找下一节点时都需要遍历整个数组，所以为了简化工作量，我们开一个1w的数组，按照每一个结点的地址来决定存放在数组中的位置，这样当我们寻找下一节点的时候可以直接通过索引。
for (int i = 0; i < num; i++) //读数据
{
cin>>ID>>Date>>NEXT;
p[ID].date=Date;
p[ID].next=NEXT;
p[ID].id=ID;
}
- 读完数据之后，我们开始对数据进行排序，定义一个成员指针的数组，用指针数组主要是考虑到空间的问题，我们可以对指针数组进行排序。这个比再赋一遍值要好得多。
这里排序的过程中会涉及的测试点6过不了的问题，我们在后面单独分析
int tk=0;
for(int i=first;i!=-1;i=p[i].next)//将数据按顺序存放到指针数组q中
{
q[tk++]=&p[i];
}
- 最后我们对已经排好序的数组进行反转操作
这里使用了一个reverse（）的函数
逆序（反转）无论是在C或是C++中用的都特别多，常用于数组，字符串，容器等，其本身的函数参数也不复杂。
标准C中是没有recerse()函数的，这是C++的一个新增函数，使用需要包含头文件
#include < algorithm >
reverse函数用于反转在[first,last)范围内的顺序（包括first指向的元素，不包括last指向的元素），reverse函数没有返回值。
例如，交换vector容器中元素的顺序
vector v = {5,4,3,2,1};
reverse(v.begin(),v.end());//v的值为1,2,3,4,5
还有string类的字符串
string str=“www.mathor.top”;
reverse(str.begin(),str.end());//str结果为pot.rohtam.wwww
最后给出函数原型，该函数等价于通过调用iter_swap来交换元素位置
template < class BidirectionalIterator >
void reverse (BidirectionalIterator first, BidirectionalIterator last)
{
while ((first!=last)&&(first!=–last))
{
std::iter_swap (first,last);
++first;
}
}
按照题意，我们通过取余的方式划分出每一块需要反转的结点，for循环结束的判定条件则是当剩余结点不够进行一次反转：
for(int i=tk,j=0;i/ty!=0;i-=ty,j+=ty)
{
reverse(q+j,q+j+ty);//逆序指针数组 原来数组存放的链表地址进行逆序
}
- 最后一步将最终结果打印出来：
for( int i=0;i<tk-1;i++)
{
printf("%05d %d %05d\n",q[i]->id,q[i]->date,q[i+1]->id);
}
printf("%05d %d -1",q[tk-1]->id,q[tk-1]->date);
- 关于测试点6的问题，这题一直卡在测试点6过不去，参考了别人的代码，一行一行的对比最后才找出问题，吐血~，这题在题目中挖了一个坑 “结点的地址是 5 位非负整数，NULL 地址用 ?1 表示。”这句话其实暗示-1也可以作为地址，而我们可能会先入为主，把 -1当作最后一个空地址，然而在输入的信息中可能会存在这样或这样一行信息
-1 1 -1
-1 3 12309
- 这就需要我们在对结点进行排序的时候，就需要将这些无效结点剔除出去，也就是判断它的地址是不是 -1
这是我之前的代码！！！！！(错误的）
for (int i = 0; i < num; i++) //读数据
{
cin>>ID>>Date>>NEXT;
p[ID].date=Date;
p[ID].next=NEXT;
p[ID].id=ID;
}
- 哈哈脑补一个测试样例：
00100 7 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218
-1 7 -1
- 我之前的代码运行结果是
- 正确结果是：
AC代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct List
{
int id;
int date;
int next;
};
int main()
{
struct List p[100000+10];//链表结构体
struct List *q[100000+10];//存放链表结构体地址的数组
int first,num,ty;
cin>>first>>num>>ty;
int ID,Date,NEXT;//暂时存放
for (int i = 0; i < num; i++) //读数据
{
cin>>ID>>Date>>NEXT;
p[ID].date=Date;
p[ID].next=NEXT;
p[ID].id=ID;
}
int tk=0;
for(int i=first;i!=-1;i=p[i].next)//将数据按顺序存放到指针数组q中
{
q[tk++]=&p[i];
}
for(int i=tk,j=0;i/ty!=0;i-=ty,j+=ty)
{
reverse(q+j,q+j+ty);//逆序指针数组 原来数组存放的链表地址进行逆序
}
for( int i=0;i<tk-1;i++)
{
printf("%05d %d %05d\n",q[i]->id,q[i]->date,q[i+1]->id);
}
printf("%05d %d -1",q[tk-1]->id,q[tk-1]->date);
return 0;
}
哈哈~这是自己第一次写博客，立个小小的flag，能坚持一个月发两篇。