C++ 实现链表反转：从数组解法到递归思路

进阶版：完整链表递归解法

为了贴合算法考察目标，这里补充完整的链表构建与递归逻辑。

#include <vector>
#include <string>
#include <iostream>
#include <sstream>

using namespace std;

// 链表节点定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode():val(0), next(nullptr){}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next): val(x), next(next) {}
};

vector<int> res;

void recur(ListNode* head) {
    if(head == nullptr) return;
    recur(head->next);
    res.push_back(head->val);
}

vector<int> reverseBookList(ListNode* head) {
    res.clear();
    recur(head);
    return res;
}

// 辅助函数：将 vector 转为链表
ListNode* vectorToListNode(const vector<int>& vec){
    if (vec.empty()) return nullptr;
    ListNode* head = new ListNode(vec[0]);
    ListNode* current = head;
    for (size_t i = 1; i < vec.size(); i++) {
        current->next = new ListNode(vec[i]);
        current = current->next;
    }
    return head;
}

int main() {
    string s;
    getline(cin, s);
    stringstream ss(s);
    int num;
    vector<int> inputVec;
    while (ss >> num) {
        inputVec.push_back(num);
    }
    
    ListNode* head = vectorToListNode(inputVec);
    vector<int> reversedRes = reverseBookList(head);
    
    for (size_t i = 0; i < reversedRes.size(); i++) {
        cout << reversedRes[i];
        if (i < reversedRes.size() - 1) {
            cout << " ";
        }
    }
    return 0;
}

核心知识点

1. 类型安全：size_t vs int

在循环中 for (size_t i = 0; i < reversedRes.size(); i++)，务必注意 reversedRes.size() 返回的是无符号整型 size_t。若使用有符号 int 进行比较，当 size() 为 0 时，i - 1 可能产生负数并转为极大正数，导致越界访问。这是 C++ 编程中常见的陷阱。

2. 输入处理三件套

getline + stringstream + >> 是 C++ 解析「空格分隔字符串」的经典组合，解决了 C 语言 scanf 无法读取整行、手动分割字符串的痛点。

• getline(cin, s)：读取整行内容。
• stringstream ss(s)：将字符串封装为流对象。
• while (ss >> num)：逐词提取整数，自动跳过空格。

3. 容器对比：C 语言 char[] vs C++ string

4. 链表构建技巧

小型单文件程序中，可以省去 std:: 前缀简化书写，但在大型项目中不建议滥用 using namespace std;。构建链表时，利用带参数的构造函数可以简化节点连接逻辑：

ListNode *node2 = new ListNode(2, node3); // 等价于先创建再赋值 next

复杂度对比

总结

从 C 过渡到 C++，核心收获在于容器的便捷性与类型安全的意识。

• 容器特性：string、vector 封装了底层内存管理，告别手动处理数组长度和字符串边界的繁琐。
• 迭代器思维：反向迭代器让容器反转变得极简，理解迭代器是 C++ 容器操作的核心。
• 算法平衡：同一道题有多种解法，需根据考察目标选择合适的实现方式，而非只追求代码简洁。

这道题是从 C 过渡到 C++ 的重要一步，后续继续刷 LeetBook 85 题，记录每道题的学习过程。