6-1 单链表逆转（20 分）
本题要求实现一个函数，将给定的单链表逆转。
函数接口定义：
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
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(){
int len = 0;
int num = 0;
PtrToNode list = NULL;
PtrToNode last = NULL;
scanf("%d",&len);
if (len==0)
{
return NULL;
}
scanf( "%d",&num );
list=(List)malloc(sizeof(struct Node));
list->Data = num;
list->Next = NULL;
last = list;
len--;
while(len){
scanf( "%d",&num );
PtrToNode node = (List)malloc(sizeof(struct Node));
node->Data=num;
node->Next = NULL;
last->Next = node;
last = node;
len--;
}
return list;
}
void Print( List L ){
if (L==NULL)
{
return ;
}
while(L!=NULL){
printf("%d ",L->Data);
L=L->Next;
}
putchar('\n');
}
List Reverse( List L ){
List t=NULL;
List newlist=NULL;
while(L!=NULL){
t=L->Next;
L->Next=newlist;
newlist=L;
L=t;
}
return newlist;
}
int main()
{
List L1, L2;
L1 = Read();
L2 = Reverse(L1);
Print(L1);
Print(L2);
return 0;
}
思路：创建一个新的链表，
第一次：L->Next=newlist;先让L这个节点指向空，而后，再把L这个节点赋给newlist.
第二次：由于newlist这个节点是之前的L节点，则数据域为3的这个节点（L->next）指向了数据域为1的这个节点，再把数据域为3的这个节点赋给newlist.
.....依次循环下去
单链表的逆转就此完成
