本题要求实现一个函数，将给定的单链表逆转。
函数接口定义：
List Reverse( List L );
其中List结构定义如下：
typedef struct Node
PtrToNode;
struct Node {
ElementType Data; /
存储结点数据
/
PtrToNode Next; /
指向下一个结点的指针
/
};
typedef PtrToNode List; /
定义单链表类型 */
L是给定单链表，函数Reverse要返回被逆转后的链表。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表
/
void Print( List L ); /
细节在此不表 */
List Reverse( List L );
int main()
{
List L1, L2;
L1 = Read();
L2 = Reverse(L1);
Print(L1);
Print(L2);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
5
1 3 4 5 2
输出样例：
1
2 5 4 3 1
这个题直接将单链表直接逆置即可，不用新建链表，但是这个PTA题目用的是没有头节点的单链表，所以错了好多次，郁闷。
对应于这个题的逆置代码：
PtrToNode Reverse(PtrToNode L)
{
PtrToNode p1=NULL,p2=NULL;
while(L!=NULL)
{
p2=L->Next;
L->Next=p1;
p1=L;
L=p2;
}
return p1;
}
逆置实际所采用的方法就是改变指针指向。
给出带有头结点的完整代码：（不适用于本题）
（改变了原来的单链表）
#include<stdio.h>
#include<stdlib.h>
typedef struct Node *PtrToNode;
struct Node
{
int data;
PtrToNode Next;
};
PtrToNode read()
{
int n;
scanf("%d",&n);
PtrToNode L,head;
L=(PtrToNode)malloc(sizeof(struct Node));
L->Next=NULL;
head=L;
int i;
for(i=1;i<=n;i++)
{
PtrToNode e=(PtrToNode)malloc(sizeof(struct Node));
scanf("%d",&e->data);
e->Next=NULL;
L->Next=e;
L=L->Next;
}
return head;
}
void Print(PtrToNode L)
{
PtrToNode p;
p=L->Next;
while(p!=NULL)
{
printf("%d ",p->data);
p=p->Next;
}
}
void Printt(PtrToNode L)
{
PtrToNode p=L;
while(p!=NULL)
{
printf("%d",p->data);
p=p->Next;
}
return ;
}
PtrToNode Reverse(PtrToNode L)
{
PtrToNode p,q;
p=L->Next;
L->Next=NULL;
while(p!=NULL)
{
q=p->Next;//指针q起牵引作用
p->Next=L->Next;//这里相当于改变了指针指向
L->Next=p;//移动，始终在p前一个结点(相对于原始链)
p=q;
}
return L;
}
int main()
{
PtrToNode L1,L2;
L1=read();
L2=Reverse(L1);
Print(L2);
return 0;
}
当指针p移动到某个位置时，让p->L所指的下一个(其实L的Next指向的就是p前边的那个)，这样就改变了指向。