[数据结构与算法]单链表逆转

要求实现一个函数，将给定的单链表逆转。

函数接口定义：

List Reverse(List L);

其中List结构定义如下：

typedef struct Node *PtrToNode;
struct Node
{
     ElementType Data; /*存储结点数据*/
     PtrToNode Next; /*指向下一个结点的指针*/
};
typedef PtrToNode List; /*定义单链表类型*/     

L是给定单链表，函数Reverse要返回被逆转的链表。

输入样例：

5
1 3 4 5 2

输出样例：

1
2 5 4 3 1

#include <iostream>
#include <stdlib.h>
using namespace std;
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node
{
    ElementType Data;
    PtrToNode Next;
};
typedef PtrToNode List;
List Read()
{
	int n;
	cin>>n;
	List L=NULL;
	PtrToNode p=NULL;
	PtrToNode q=L;
	for(int i=0;i<n;i++)
	{
		p=(PtrToNode)malloc(sizeof(struct Node));  //创建结点p，分配空间
		cin>>p->Data;
		p->Next=NULL;
		if(i==0)   
		{
			L=p;
			q=p;
		}
		else 
		{
			q->Next=p;
			q=q->Next;
		}
	}
	return L;
}
void Print(List L)
{
	PtrToNode q=L;
	while(q)
	{
		cout<<q->Data<<" ";
		q=q->Next;
	}
	cout<<endl;
}
List Reverse(List L)
{
	List ReL;
	PtrToNode q,r,s;
	if(L==NULL||L->Next==NULL)  //若为空表或只有一个结点，则返回
	{
		return L;
	}
	q=L;
	r=q->Next;
	s=r->Next;	
	q->Next=NULL;
	while(r)
	{
		r->Next=q;
		q=r;
		r=s;
		if(s)
		{
			s=s->Next;
		}
	}	
	ReL=q;
	return ReL;
	
}
int main()
{
    List L1, L2;
    L1 = Read();
    L2 = Reverse(L1);
    Print(L1);
    Print(L2);
    return 0;
}