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

函数接口定义： List Reverse( List L ); 其中List结构定义如下： typedef struct Node *PtrToNode; struct Node {    ElementType Data; /* 存储结点数据 */    PtrToNode   Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */ L是给定单链表，函数Reverse要返回被逆转后的链表。

#include <iostream>

using namespace std;

typedef struct Node *PtrToNode;
struct Node {
    int Data; // 存储结点数据
    PtrToNode Next; // 指向下一个结点的指针
};
typedef PtrToNode List; // 定义单链表类型

List CreateList(int n); // 创建链表
void PrintList(List L); // 输出链表
List Reverse(List L); // 单链表逆转

int main() {
    int n;
    cin >> n; // 输入链表长度
    List L = CreateList(n); // 创建链表
    cout << "Original List: ";
    PrintList(L); // 输出原链表
    L = Reverse(L); // 单链表逆转
    cout << "Reversed List: ";
    PrintList(L); // 输出逆转后的链表
    return 0;
}

List CreateList(int n) {
    List L = NULL, tail = NULL;
    for (int i = 0; i < n; i++) {
        int data;
        cin >> data; // 输入节点数据
        PtrToNode newNode = new Node; // 创建新节点
        newNode->Data = data; // 节点数据赋值
        newNode->Next = NULL; // 节点next指针置为空
        if (L == NULL) {
            L = newNode; // 第一个节点
        } else {
            tail->Next = newNode; // 将新节点链接到链表尾部
        }
        tail = newNode; // 更新链表尾指针
    }
    return L;
}

void PrintList(List L) {
    while (L != NULL) {
        cout << L->Data << " ";
        L = L->Next;
    }
    cout << endl;
}

List Reverse(List L) {
    if (L == NULL || L->Next == NULL) {
        return L; // 空链表或只有一个节点，直接返回
    }
    // 迭代法
    // PtrToNode pre = nullptr, cur = L, nxt = nullptr;
    // while (cur != nullptr) {
    //     nxt = cur->Next; // 记录下一个节点
    //     cur->Next = pre; // 当前节点的next指针指向前一个节点
    //     pre = cur; // 更新前一个节点
    //     cur = nxt; // 更新当前节点
    // }
    // return pre; // 返回新的头节点
    // 递归法
    PtrToNode newHead = Reverse(L->Next); // 递归到链表尾部，得到新的头节点
    L->Next->Next = L; // 将当前节点的next指针指向前一个节点
    L->Next = NULL; // 将当前节点的next指针置为空，防止形成环
    return newHead; // 返回新的头节点
}

typedef struct Node *PtrToNode; 这条语句的意思是：将 struct Node * 类型定义为 PtrToNode 类型，方便后续使用。在 C 语言中，由于 struct 关键字必须出现在结构体名称前面，因此使用结构体指针类型需要写成 struct Node *，比较繁琐。为了方便使用，可以使用 typedef 来给结构体指针类型取一个简短的别名，这样就可以写成 PtrToNode，代码更加简洁。

例如，在下面的代码中，PtrToNode 就是 struct Node * 的别名：

typedef struct Node *PtrToNode;

struct Node {
    int data;
    PtrToNode next;
};

PtrToNode create_node(int data) {
    PtrToNode p = malloc(sizeof(struct Node));
    p->data = data;
    p->next = NULL;
    return p;
}

这样就可以通过 PtrToNode 类型来声明一个结构体指针变量，例如：

PtrToNode p = create_node(123);

运行程序，输入如下样例数据：
6
1 2 3 4 5 6

程序将输出如下结果：

Original List: 1 2 3 4 5 6 
Reversed List: 6 5 4 3 2 1