实验4-原地逆转链表（梅开二度）

题目：

设计一个算法，将不带头节点的单链表所有结点的连接方向“原地”逆转，即要求利用原表的存储空间。

代码：

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
void InitList(LinkList &L)
{
	L=NULL;
}
void visit(LinkList L)
{
	while(L){
		cout<<L->data<<" ";
		L=L->next;
	}
	cout<<endl;
}
void TailInsert(LinkList &L)
{
	InitList(L);
	ElemType e;
	cin>>e;
	if(e!=9999){
		L=new LNode;
		L->data=e;
		L->next=NULL;
	}
	LinkList p=NULL;
	LinkList r=L;
	cin>>e;
	while(e!=9999){
		p=new LNode;
		p->data=e;
		r->next=p;
		r=p;
		cin>>e;
	}
	r->next=NULL;
}
void ReverseList(LinkList &L)
{
	if(L==NULL && L->next==NULL) return;
	LinkList p,q,r;
	p=L;
	q=p->next;
	r=q->next;
	p->next=NULL;
	while(r){
		q->next=p;
		p=q;
		q=r;
		r=r->next;
	}
	q->next=p;
	L=q;
}
int main()
{
	LinkList L;
	InitList(L);
	TailInsert(L);//1 2 3 4 5 9999
	visit(L);
	ReverseList(L);
	visit(L);
	return 0;
}

输入输出示例

#include <iostream>
using namespace std;
typedef int ElemType;
typedef struct LNode{
	ElemType data;
	struct LNode *next;
}LNode,*LinkList;
void InitList(LinkList &L)
{
	L=NULL;
}
void visit(LinkList L)
{
	while(L){
		cout<<L->data<<" ";
		L=L->next;
	}
	cout<<endl;
}
void TailInsert(LinkList &L)
{
	InitList(L);
	ElemType e;
	cin>>e;
	if(e!=9999){
		L=new LNode;
		L->data=e;
		L->next=NULL;
	}
	LinkList p=NULL;
	LinkList r=L;
	cin>>e;
	while(e!=9999){
		p=new LNode;
		p->data=e;
		r->next=p;
		r=p;
		cin>>e;
	}
	r->next=NULL;
}
void ReverseList(LinkList &L)
{
	if(L==NULL && L->next==NULL) return;
	LinkList p,q,r;
	p=L;
	q=p->next;
	r=q->next;
	p->next=NULL;
	while(r){
		q->next=p;
		p=q;
		q=r;
		r=r->next;
	}
	q->next=p;
	L=q;
}
int main()
{
	LinkList L;
	InitList(L);
	TailInsert(L);//1 2 3 4 5 9999
	visit(L);
	ReverseList(L);
	visit(L);
	return 0;
}