6-1 单链表逆转

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
思路：这个题目第一次看以为有点儿问题，没有给出单链表的输入函数和输出函数，所以无从知道有没有头结点。而且输出也有问题怎么Print(L1)输出只有一个1？然而这些无疑都是在给题目增加难度（二十分的题呢！）。需要注意的是输出的那个一是原单链表头部的那个一，不觉得很神奇嘛？确定题目没有BUG？还是理解为给题目增加难度吧。有没有头结点自己可以去试试，我的答案是该题不带头结点。最后函数内的东西就是遍历L1的同时L2使用单链表的前插法。


以下是AC代码：

List Reverse(List L)
{
    List Lcopy = NULL, temp = NULL;
    while (L!=NULL)
    {
        temp=L->Next;
        L->Next = Lcopy;
        Lcopy = L;
        L = temp;
    }
    return Lcopy;

}

下面是调试用的完整代码：

#include <stdio.h>
#include <stdlib.h>
#include<iostream>
using namespace std;
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;
}
List Read()
{
    int n; scanf("%d", &n);
    List list=NULL, temp, p;
    if (n >= 1){
        list = (List)malloc(sizeof(Node));
        scanf("%d", &list->Data);
        list->Next = NULL; n--;
    }

    p = list;
    while (n--){
        temp = new Node();
        scanf("%d", &temp->Data);
        
        temp->Next = p->Next;
        p->Next = temp;
        p = p->Next;
        
    }

    
    return list;
}
void Print(List L)
{
    List temp = L;
    while (temp != NULL){
        cout << temp->Data << " ";
        temp = temp->Next;
    }
    putchar('
');
}
List Reverse(List L)
{
    List Lcopy = NULL, temp = NULL;
    while (L!=NULL)
    {
        temp=L->Next;
        L->Next = Lcopy;
        Lcopy = L;
        L = temp;
    }
    return Lcopy;

}