C++ PAT数据结构基础02-1题 反转单链表

Question

题目大意：反转单链表，给定常数K和单链表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.

输入说明：每次输入一个案例，对每个案例，第一行内容是链表第一个节点的地址，节点数N(N<=100,000)（不一定是最终形成的单链表的节点数），常数K(<=N),K是需要反转的子链表的长度，节点的地址是一个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

我的代码如下：
/* PAT数据结构基础习题02-1题 */
#include
using namespace std;

const int Maxn=100001;
typedef struct{
int addr;
int value;
int nextaddr;
}Node; //结构数组元素，存储三个元素
typedef struct tagnode{
Node *n;
struct tagnode *nextp;
}LNode; //链表节点，用于存储下一节点地址，和数组元素地址

int main()
{
Node nodes[Maxn]; //建立数组来存储输入的信息，排列顺序根据输入的顺序值
int firaddr,num,k;
cin>>firaddr>>num>>k;
nodes[0].value=num;
nodes[0].addr=nodes[0].nextaddr=0; //数组大小为100001,存储从1开始，因而0节点随意赋值
int i,j;
Node pnode;
for(i=0;i {
cin>>pnode.addr>>pnode.value>>pnode.nextaddr;
nodes[pnode.value]=pnode;
}
// for(i=1;i<=num;i++)
// {
// cout< // cout // cout // }
LNode *head,*pt; //建立LNode的链表
head->n=&nodes[0];
head->nextp=NULL; //头结点的初始化
pt=head;
for(i=0;i {
for(j=k;j>0;j--)
{
LNode *pp=new LNode;
pp->n=&nodes[i*k+j];
pt->nextp=pp;
pt=pt->nextp;
delete pp;
}
}
if(i*k {
for(j=1;i*k+j {
LNode *pp=new LNode;
pp->n=&nodes[i*k+j];
pt->nextp=pp;
pt=pt->nextp;
delete pp;
}
}
pt->nextp=NULL; //将链表结尾节点下一地址置为空
pt=head->nextp; //pt指针移动到头指针的下一节点，开始循环输出
while(pt!=NULL)
{
cout<n->addr<<" "<n->value<<" "<n->nextaddr< pt=pt->nextp;
}
return 0;
}
求大神指导啊！！！

Answer 1

看了你的程序，感觉你的解题思路如下：
（1）把输入全部读取到nodes的数组中，并且以data为下表存放
（2）从data=k开始向前扫描nodes到1，并且把扫描结果存放到以head开头的链表中，
（3）从max data开始向前扫描nodes到k+1，并且把扫描结果添加到上述链表中，
（4）输出链表
不知道我的理解是否正确。解题思路应该没有什么大问题。
但是这样有一个局限性，也就是输入数据中的data必须从1到n要连续存在。否则nodes[x]会不存在。而题目对输入数据并没有这样的限制。不知道我对题目的理解是否正确。
我觉得算法和数据结构上还可以稍作优化。
可以用nodes数组直接存储输入的链表结构，以nodes下标为地址，value域存储data，nextaddr存储指向的下一个地址。
计算时可以利用堆栈，按以下步骤计算：
（1）从nodes链表的头看是扫描，并且把每个节点压入堆栈，直到node.value == K。并且记住K的下标。
（2）把堆栈中的节点弹出并且打印。
（3）从K的下标开始直到N，扫描并且重复（1）（2）。

另外如果题目允许使用双向链表，也可以把nodes设计成双向链表，读取输入完成后，扫描nodes，补充完成preaddr指针。接下来从K的节点开始反向扫描链表并且打印就行。

另外程序设计上有一个严重问题。在扫描nodes保存到链表的过程中，不能delete pp。因为pp所申请的空间用于链表存储，以后还要用到。应该在打印完成后，扫描并且删除链表，释放空间。