Question

数据结构 单链表 就地逆置 C++ 不允许申请新的节点空间 输入输出顺序一样

实现如下操作：根据键盘输入的n个整型元素建立单链表（要求单链表的元素顺序和输入的元素顺序一致），要求将单链表原地逆置（在逆置过程中不能申请新的结点空间），输出逆置后的元素序列，要求元素和元素之间用空格隔开。

Answer 1

#include<iostream>

using namespace std;

struct Data
{
int d;
struct Data *next;
};

//创建链表
Data* create()
{
int i,n;
Data *h,*p,*q;

cout<<"请输入链表节点的数量：";
cin>>n;
if(n>0)
{
h=q=new Data();
cout<<"请输入第1个链表节点的数据（整数）：";
cin>>h->d;
for(i=2;i<=n;i++)
{
p=new Data();
cout<<"请输入第"<<i<<"个链表节点的数据（整数）：";
cin>>p->d;
q->next=p;
q=p;
}
q->next=NULL;
}
return h;
}
//输出链表的数据
void output(Data *h)
{
while(h)
{
cout<<h->d;
if(h->next)
{
cout<<" ";
}
h=h->next;
}
cout<<endl;
}
//逆转链表
Data* reverse(Data *h)
{
Data *p=h,*q=NULL;

if(h)
{
p=p->next;
h->next=NULL;
}
while(p)
{
q=p->next;
p->next=h;
h=p;
p=q;
}
return h;

}
//释放链表
void free(Data *h)
{
Data *p=h;

while(p)
{
h=h->next;
delete p;
p=h;
}
}
int main()
{
Data *h=create();
cout<<"链表逆转前："<<endl;
output(h);
h=reverse(h);
cout<<"链表逆转后："<<endl;
output(h);
free(h);
return 0;
}