单链表逆转

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.
.....依次循环下去
单链表的逆转就此完成