题目描述

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

//函数接口定义：
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);
    return 0;
}

List Read(){
    List L,head;
    int num;
    int i;
    scanf("%d",&num);
    head=L=(List)malloc(sizeof(struct Node));///头结点
    L->Next=NULL;
    for(i=0;i<num;i++){
        L->Next=(List)malloc(sizeof(struct Node));
        scanf("%d",&L->Next->Data);
        L=L->Next;
    }
    L->Next=NULL;
    return head;
}
/*这里是对不带头结点的链表进行逆转*/
List Reverse( List L ){
    List S;
    struct Node *temp;//定义一个临时节点，用来存放要从原链表取出即将插入新链表的那个节点
    S=(List)malloc(sizeof(struct Node));//定义一个新链表
    S->Next=NULL;
    while(L!=NULL){
        temp=L;//取原链表的第一个节点
        L=L->Next;
        temp->Next=S->Next;//插入到新链表的头结点后面
        S->Next=temp;
    }
    return S->Next;//返回不带头结点的链表即返回头结点的下一个
}

void Print( List L ){
    List N;
    N=L;
    while(N->Next!=NULL){
        printf("%d ",N->Next->Data);
        N=N->Next;
    }
}