题意概括

给定一个单向链表，要求将其进行反转。

输入格式:

• 输入包含多组测试数据。
• 每组数据的第一行是一个整数 n，表示链表的长度。
• 第二行是 n 个整数，代表链表每个节点的值。
• 当 n 为 0 时，表示一个空链表。

输出格式:

• 对于每组测试数据，输出一行反转后链表的节点值，值与值之间用空格隔开，行末不能有-多余的空格。

数据范围:

• $0 \le n \le 5000$

基础知识

本题是链表操作中最基础且最核心的问题之一，旨在考察对链表指针操作的熟练程度。解决此问题主要有两种主流方法：迭代法 (Iteration) 和 递归法 (Recursion)。在工业界和竞赛中，迭代法因其 $O(1)$ 的空间复杂度和更低的函数调用开销而更为常用。

迭代法 (Iterative Approach):

迭代法的核心思想是在遍历原始链表的同时，逐个地将节点的 next 指针“掉头”，使其指向前一个节点。为了在改变指针方向时，依然能够找到后续的节点，我们需要借助额外的指针来保存状态。

算法流程:

我们通常需要三个指针来辅助完成整个反转过程：

1. pre (previous): 该指针始终指向当前节点 cur 的前一个节点。在反转后，pre 将成为 cur 的后继节点。对于原始的头节点，它的前面没有节点，因此 pre 的初始值为 nullptr。
2. cur (current): 该指针指向我们当前正在操作的节点。它的初始值为链表的头节点 head。
3. nxt (next): 该指针用于临时存储cur 节点的原始下一个节点。这是必需的，因为我们下一步就要修改 cur->next 的指向，如果不预先保存，我们就会丢失与后续链表的连接。

整个遍历和反转的步骤如下：

1. 初始化 pre = nullptr, cur = head。
2. 进入一个循环，条件是 cur 不为 nullptr。
3. 在循环内部： a. 首先，用 nxt 保存 cur 的下一个节点：nxt = cur->next。 b. 核心操作：反转指针。将 cur 的 next 指针指向它的前一个节点 pre：cur->next = pre。 c. 为下次迭代做准备: 将 pre 和 cur 指针都向前“移动”一步。即 pre 更新为 cur，cur 更新为 nxt：pre = cur; cur = nxt;。
4. 当循环结束时，cur 会指向 nullptr，而 pre 指针将指向原始链表的最后一个节点，也就是反转后新链表的头节点。返回 pre 即可。

复杂度分析:

• 时间复杂度: 算法需要从头到尾遍历链表一次，因此时间复杂度为 $O(N)$，其中 $N$ 是链表的节点数。
• 空间复杂度: 算法只使用了固定的几个指针变量，与链表的大小无关，因此空间复杂度为 $O(1)$。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

// 定义链表节点结构体
struct Node {
    int val;
    Node* nxt;
    Node(int x) : val(x), nxt(nullptr) {}
};

// 迭代法反转链表
Node* rev(Node* head) {
    Node* pre = nullptr;
    Node* cur = head;

    while (cur) {
        Node* nxt = cur->nxt; // 临时保存下一个节点
        cur->nxt = pre;       // 反转指针
        pre = cur;            // pre 向前移动
        cur = nxt;            // cur 向前移动
    }
    return pre; // 返回新的头节点
}

void slv(int n) {
    if (n == 0) {
        cout << endl;
        return;
    }

    Node* head = nullptr;
    Node* tail = nullptr;

    // 根据输入构建链表
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        Node* node = new Node(x);
        if (!head) {
            head = tail = node;
        } else {
            tail->nxt = node;
            tail = node;
        }
    }

    // 反转链表
    head = rev(head);

    // 打印反转后的链表
    Node* cur = head;
    while (cur) {
        cout << cur->val;
        if (cur->nxt) {
            cout << " ";
        }
        cur = cur->nxt;
    }
    cout << endl;

    // 释放链表内存
    cur = head;
    while (cur) {
        Node* tmp = cur;
        cur = cur->nxt;
        delete tmp;
    }
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    while (cin >> n) {
        slv(n);
    }

    return 0;
}

/*
样例输入 1:
5
1 2 3 4 5

样例输出 1:
5 4 3 2 1

样例输入 2:
0

样例输出 2:

*/