数据结构与算法----1.7 对单链表就地逆置

[c++]代码库

//***********************************
//功能：对单链表就地逆置
//日期：2017年9月27日
//作者：Ryan2019
//***********************************
#include <iostream>
using namespace std;
typedef int LElemType;
typedef struct LNode
{
    LElemType data;
	LNode *next;
}* LList;
void ListCreate(LList &L,int n,LElemType a[]);//创建链表
void Listshow(LList &L);//显示链表
void ListReverse(LList &L);//对单链表就地逆置

int main()
{
	LList L; int n=4;
	LElemType a[4]={1,2,3,4};
	ListCreate(L,n,a);
	cout<<"原链表为：";	Listshow(L);
	ListReverse(L);
	cout<<"逆置后链表为：";	Listshow(L);
	return 0;
}

void ListCreate(LList &L,int n,LElemType a[])
{
	LList p;	int i;
	L=new LNode; L->next=NULL;
	for(i=n-1;i>=0;i--)
	{
		p=new LNode;
		p->data=a[i];
		p->next=L->next;
		L->next=p;
	}
}
void Listshow(LList &L)
{
	LList p;
	for(p=L->next;p;p=p->next)
	{
		cout<<p->data<<" ";
	}
	cout<<endl;
}
void ListReverse(LList &L)
{
	if(L==NULL||L->next==NULL||L->next->next==NULL)
	{
		return;
	}
	LList p,q;
	p=L->next;
	while(p->next)
	{
		q=p->next;
		if(q->next)
		{
			p->next=q->next;
		}
		else
		{
			p->next=NULL;
		}
		q->next=L->next;
		L->next=q;
	}

}