C++ 算法实战：图书整理 I（反转链表）从 C 到 C++ 的过渡

核心知识点

类型安全与 size_t

在循环条件 for (size_t i = 0; i < reversedRes.size(); i++) 中，注意 reversedRes.size() 返回的是无符号整型 size_t。如果循环变量定义为 int，当 size 较大时可能导致比较异常。建议统一使用 size_t。

输入处理三件套

C++ 解析「空格分隔的字符串」的经典组合是 getline + stringstream + >>：

1. getline(cin, s)：读取整行输入，避免 cin >> s 遇到空格截断的问题。
2. stringstream ss(s)：将字符串封装为流对象，后续可通过 >> 像从键盘读取一样提取数据。
3. while (ss >> num)：只要流中还有可提取的整数，循环就会执行；到达末尾自动终止。

Vector 与 String 的优势

相比 C 语言的 char[] 和固定数组，C++ 标准库提供了更安全的封装：

• Vector：动态数组，无需预先定义长度，push_back 自动扩容。
• String：内置内存管理，支持 + 拼接、[] 访问，不易越界。

其他反转方式

除了反向迭代器，还可以使用 std::reverse 函数（需包含 <algorithm>）：

vector<int> reversedRes = res;
reverse(reversedRes.begin(), reversedRes.end());

两种方式均可，反向迭代器构造更简洁，reverse 适合需要保留原容器的场景。

标准解法对比：链表 + 递归

虽然上述数组解法实现了功能，但题目核心考察的是「链表操作」。LeetCode 等平台的经典解法通常采用「递归 + 链表」的方式。

递归思路原理

递归的核心是「递推到链表末端，回溯时收集节点值」：

1. 终止条件：当 head == nullptr 时，代表遍历到链表尾。
2. 递推工作：递归访问下一个节点 head->next。
3. 回溯阶段：从末端开始，依次将当前节点值加入结果列表，实现反转。

class Solution {
public:
    vector<int> reverseBookList(ListNode* head) {
        recur(head);
        return res;
    }
private:
    vector<int> res;
    void recur(ListNode* head) {
        if(head == nullptr) return;
        recur(head->next);
        res.push_back(head->val);
    }
};

为了完整运行，我们需要补充链表结构定义及主函数入口：

#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;
}

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;
}

复杂度对比

总结

通过这道题，可以体会到从 C 到 C++ 的几个核心转变：

• 容器便捷性：string、vector 等标准库封装了底层内存管理，告别手动处理数组长度和字符串边界的繁琐。
• 输入处理升级：getline + stringstream 是解析整行输入的黄金组合。
• 迭代器思维：理解 rbegin()/rend() 让容器操作变得极简。
• 类型安全：关注 size_t 与 int 的差异，避免边界错误。
• 算法平衡：同一道题有多种解法，需根据考察目标选择合适的实现方式。