写在前面

想在现有的技术栈上，提高 C++ 的技能点。

这是新时代的学习方法：AI托举，边做边学。

做题

这道题出现在腾讯WXG后台一面的考察中（牛客网@MRWu_haha分享），所以想试试。

做题思路

这里难的是怎么捋顺“递归”的解题思路。

先明确，递归的作用是：

• 将问题分解为更小的子问题，直到达到一个简单的基本情况（base case），然后逐步组合结果。
• 提供对数据（链表）从尾到头的访问机会。

递归的关键在于：我们信任递归调用能正确处理好子问题，我们只需要处理当前节点和子结果之间的连接。

1. 递归范式：

1. 1. 判空退出
   2. 递归赋值

1. 根据上述递归判断条件 base case，操作 尾部元素。

题解

/**
 * Definition for singly-linked list.
 * 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) {}
 * };
 */
/// ************************ 简单方法，哈哈哈哈哈
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        vector<int> v;
        ListNode* new_head = head;
        while (new_head) {
            v.push_back(new_head->val);
            new_head = new_head->next;
        }
        reverse(v.begin(), v.end());
        new_head = head;
        for (int i = 0; i < v.size(); i++) {
            new_head->val = v[i];
            new_head = new_head->next;
        }
        return head;
    }
};


/// ************************ 递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归范式1: 判空推出（base case）
        if (!head || !head->next) {
            return head;
        }
        // 递归范式2: 递归赋值
        ListNode* lastNode = reverseList(head->next);
        // *********************** 最后元素的访问机会 | START
        // 1>> next_node 是当前节点的下一个节点（即子链表的原头节点）
        ListNode* next_node = head->next; 
        // 2>> 链表指向反转：将子链表的尾节点（现在指向nullptr）的next指向当前节点
        next_node->next = head; 
        // final>> 最后的节点不指向 nullptr 会形成环，即 1 <--> 2 <-- 3 <-- 4 <-- 5
        head->next = nullptr; 
        // *********************** 最后元素的访问机会 | END
        return lastNode; // 返回反转后链表的头节点（即原链表的尾节点）
    }
};

知识点

1. 左值引用以及右值引用

• 左值引用：对存储空间/内存的指向别名，编译时处理，不占用运行时开销（因此指向的变量必须初始化/分配内存）

int x = 10;        // 在内存中分配4字节，假设地址为 0x1000
int& ref = x;      // ref 是 x 的别名，不占用额外存储空间

// 编译器的视角：
// ref 和 x 指向同一块内存地址 0x1000
// 对 ref 的操作就是对 x 的操作

// 实用场景
void processLargeObject(const std::vector<int>& data) {
    // 传递引用，避免vector的深拷贝
    for (int val : data) {
        // 处理数据
    }
}

• 右值引用：临时对象的"接管者"，实现资源转移，提升性能

• • 延长生命周期 vs 变量赋值

int&& rref = 10;  // 临时对象 10 的生命周期被延长

// 编译器处理：
// 1. 创建临时对象存储 10
// 2. rref 绑定到这个临时对象
// 3. 临时对象生命周期延长到 rref 的作用域结束

// 实用场景：
class UniqueArray {
    int* data;
    size_t size;
public:
    // 移动构造函数
    UniqueArray(UniqueArray&& other) noexcept 
        : data(other.data), size(other.size) {
        other.data = nullptr;  // 重要！置空原对象
        other.size = 0;
    }
    
    // 移动赋值运算符
    UniqueArray& operator=(UniqueArray&& other) noexcept {
        if (this != &other) {
            delete[] data;        // 释放当前资源
            data = other.data;    // 窃取资源
            size = other.size;
            other.data = nullptr;
            other.size = 0;
        }
        return *this;
    }
};

2. 成员初始化列表

黄金法则：对于类类型成员，总是优先使用初始化列表！

2.1. 基本使用：

ClassName::ClassName(parameters) 
    : member1(value1), member2(value2), member3(value3) {
    // 构造函数体
}

// *********** 示例
class Example {
    int x;
    std::string str;
public:
    Example(int val, const std::string& s) 
        : x(val), str(s) {  // 直接初始化
        // x 和 str 在进入函数体前就已经构造完成
    }
};
//  等同于
class Example {
    int x;
    std::string str;
public:
    Example(int val, const std::string& s) {
        // 先默认构造，再赋值
        x = val;     // 赋值操作
        str = s;     // 赋值操作
    }
};

2.2. 初始化顺序：由成员在类中的声明顺序决定，与初始化列表中的顺序无关！

class OrderExample {
    int a;
    int b;
public:
    OrderExample(int x) : b(x), a(b + 1) {  // ❌ 危险！
        // 实际初始化顺序：先 a，后 b
        // 所以 a = b + 1 中的 b 是未初始化的！
    }
    
    // 正确做法：
    OrderExample(int x) : a(x + 1), b(x) {  // ✅ 正确
    }
};

2.3. 必须使用 初始化列表

(1) const 成员

(2) 引用 成员

// 1. const 成员
class ConstExample {
    const int maxValue;
public:
    ConstExample(int max) : maxValue(max) {  // ✅ 正确
        // maxValue = max;  // ❌ 错误！const 成员不能赋值
    }
};

// 2. 引用成员
class RefExample {
    int& ref;
public:
    RefExample(int& value) : ref(value) {  // ✅ 正确
        // ref = value;  // ❌ 错误！引用必须初始化
    }
};

2.4. C++11：委托构造函数

class Person {
    std::string name;
    int age;
public:
    Person() : Person("Unknown", 0) {}  // 委托给下面的构造函数
    
    Person(const std::string& n, int a) : name(n), age(a) {}
};

2.5. C++14：成员初始化器

class ModernExample {
    int defaultValue = 42;           // 类内成员初始化
    std::string name = "default";
    
public:
    ModernExample() = default;       // 使用默认值
    
    ModernExample(const std::string& n) : name(n) {}  // 覆盖默认值
};

3. default和delete等字段

class ModernBase {
public:
    virtual ~ModernBase() = default;  // 虚析构函数
    
    // 接口方法
    virtual void process() = 0;                    // 纯虚函数
    virtual void calculate(int x) { /* 默认实现 */ } // 虚函数
    
    // 工具方法
    constexpr static int getVersion() { return 1; }  // 编译时常量函数
    
    // 禁止拷贝
    ModernBase(const ModernBase&) = delete;
    ModernBase& operator=(const ModernBase&) = delete;
};

class ModernDerived final : public ModernBase {  // final 类
public:
    void process() override {  // override 确保正确重写
        std::cout << "Processing...\n";
    }
    
    void calculate(int x) final override {  // final + override
        std::cout << "Calculating: " << x * 2 << "\n";
    }
    
    // 允许移动
    ModernDerived(ModernDerived&&) = default;
    ModernDerived& operator=(ModernDerived&&) = default;
    
    // 编译时方法
    consteval static int compute(int x) {
        return x * x * x;
    }
};