大家好！欢迎来到第十四期C++面试题系列，今天我们将深入探讨数据结构相关的经典题目。数据结构是面试中的核心内容，掌握这些不仅能提升你的编程能力，还能让你在面试中脱颖而出。😊本文会逐一讲解每个问题，包括算法思路、C++代码实现，以及一些关键细节。文章结构清晰，确保你一步步理解！每个问题都配有详细代码，让我们开始吧！

---

🧩 1. 手撕单链表原地逆转

问题描述：实现单链表的原地逆转（即不占用额外空间）。
思路：使用三个指针（prev、curr、next）遍历链表。每次迭代中，反转curr节点的指向，然后移动指针。时间复杂度 $O(n)$，空间复杂度 $O(1)$。

C++代码：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
    ListNode *prev = nullptr;
    ListNode *curr = head;
    while (curr != nullptr) {
        ListNode *next = curr->next; // 保存下一个节点
        curr->next = prev; // 反转指向
        prev = curr; // 移动prev
        curr = next; // 移动curr
    }
    return prev; // 新头节点
}

// 测试代码示例
int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    ListNode *newHead = reverseList(head); // 逆转后头节点
    while (newHead) {
        cout << newHead->val << " ";
        newHead = newHead->next;
    }
    // 输出: 3 2 1
    return 0;
}

💡 小贴士：注意边界情况，如空链表或单节点链表。代码中prev初始为nullptr，确保逆转后尾节点指向空。

---

🔗 2. 手撕合并有序链表

问题描述：合并两个升序链表，返回新链表。
思路：使用一个虚拟头节点（dummy node）简化操作。比较两个链表当前节点的值，将较小者接入新链表。时间复杂度 $O(n+m)$，空间复杂度 $O(1)$。

C++代码：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0); // 虚拟头节点
    ListNode *tail = &dummy; // 尾指针
    while (l1 && l2) {
        if (l1->val <= l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2; // 处理剩余节点
    return dummy.next; // 返回真实头节点
}

// 测试代码示例
int main() {
    ListNode *l1 = new ListNode(1);
    l1->next = new ListNode(3);
    ListNode *l2 = new ListNode(2);
    l2->next = new ListNode(4);
    ListNode *merged = mergeTwoLists(l1, l2);
    while (merged) {
        cout << merged->val << " ";
        merged = merged->next;
    }
    // 输出: 1 2 3 4
    return 0;
}

😊 趣味点：用虚拟头节点避免空指针问题，代码更简洁！

---

🔍 3. 二分查找

问题描述：在有序数组中查找目标值，返回索引（未找到返回-1）。
思路：每次比较中间元素，缩小搜索范围。索引计算用 $mid=low+(high-low)/2$ 防溢出。时间复杂度 $O(\log n)$。

C++代码：

#include <vector>
using namespace std;

int binarySearch(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // 防溢出
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return -1; // 未找到
}

// 测试代码示例
int main() {
    vector<int> nums = {1, 3, 5, 7, 9};
    cout << binarySearch(nums, 5); // 输出: 2
    return 0;
}

🚀 优化：确保数组有序，否则二分查找无效哦！

---

🎯 4. 删除链表的倒数第N个节点

问题描述：删除链表中倒数第N个节点，返回头节点。
思路：快慢指针法。快指针先走N步，然后快慢指针同时移动。当快指针到末尾时，慢指针指向待删除节点的前驱。时间复杂度 $O(n)$。

C++代码：

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode dummy(0);
    dummy.next = head;
    ListNode *fast = &dummy;
    ListNode *slow = &dummy;
    // 快指针先走n步
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }
    // 同时移动，直到快指针到末尾
    while (fast->next) {
        fast = fast->next;
        slow = slow->next;
    }
    // 删除节点
    ListNode *toDelete = slow->next;
    slow->next = slow->next->next;
    delete toDelete; // 释放内存
    return dummy.next;
}

// 测试代码示例
int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    ListNode *newHead = removeNthFromEnd(head, 2); // 删除倒数第2个
    while (newHead) {
        cout << newHead->val << " ";
        newHead = newHead->next;
    }
    // 输出: 1 3
    return 0;
}

💡 注意：处理删除头节点的情况，使用虚拟头节点避免错误。

---

🔄 5. 链表中环的检测

问题描述：如果链表有环，返回入环的第一个节点；无环返回null。
思路：快慢指针法（Floyd算法）。先检测环：快指针每次走两步，慢指针走一步，若相遇则有环。然后找入环节点：重置一个指针到头，以相同速度移动直到相遇。时间复杂度 $O(n)$。

C++代码：

ListNode *detectCycle(ListNode *head) {
    if (!head || !head->next) return nullptr;
    ListNode *slow = head;
    ListNode *fast = head;
    // 检测环
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) break; // 相遇
    }
    if (slow != fast) return nullptr; // 无环
    // 找入环节点
    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

// 测试代码示例
int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = head->next; // 创建环
    ListNode *entry = detectCycle(head);
    if (entry) cout << "环入口值: " << entry->val; // 输出: 环入口值: 2
    return 0;
}

😊 趣味点：像追及问题，快慢指针的数学证明很有趣哦！

---

😄 6. 快乐数判断

问题描述：判断一个数 $n$ 是否为快乐数。快乐数定义：重复计算各位数字平方和，最终变为1；否则无限循环。
思路：模拟过程，用哈希集合记录出现过的数字。如果出现1则返回true；如果重复则false。计算平方和：$s=\sum ({\text{digit}}^2)$。

C++代码：

#include <unordered_set>
using namespace std;

int getSum(int n) {
    int sum = 0;
    while (n) {
        int digit = n % 10;
        sum += digit * digit; // 平方和
        n /= 10;
    }
    return sum;
}

bool isHappy(int n) {
    unordered_set<int> seen;
    while (n != 1 && seen.find(n) == seen.end()) {
        seen.insert(n);
        n = getSum(n);
    }
    return n == 1;
}

// 测试代码示例
int main() {
    cout << boolalpha << isHappy(19); // 输出: true (1^2 + 9^2=82, 8^2+2^2=68, ... 最终1)
    return 0;
}

🚀 优化：使用集合防循环，时间复杂度 $O(\log n)$ per step。

---

🌳 7. 二叉树的前序遍历（递归+循环）

问题描述：实现二叉树的前序遍历（根-左-右）。
思路：

• 递归：简单直接。
• 循环：用栈模拟，先压入根节点，然后循环弹出并访问，再压入右子节点、左子节点（注意顺序）。

C++代码：先定义二叉树结构。

#include <stack>
#include <vector>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 递归版本
void preorderRecursive(TreeNode* root, vector<int>& res) {
    if (!root) return;
    res.push_back(root->val); // 访问根
    preorderRecursive(root->left, res); // 左子树
    preorderRecursive(root->right, res); // 右子树
}

// 循环版本
vector<int> preorderIterative(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        res.push_back(node->val); // 访问根
        if (node->right) stk.push(node->right); // 先右后左，确保左先访问
        if (node->left) stk.push(node->left);
    }
    return res;
}

// 测试代码示例
int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    vector<int> rec = preorderRecursive(root, vector<int>());
    vector<int> iter = preorderIterative(root);
    for (int val : iter) cout << val << " "; // 输出: 1 2 3
    return 0;
}

💡 小贴士：循环版本中，栈的顺序是后进先出，所以先压右节点。

---

🌿 8. 二叉树的中序遍历（递归+循环）

问题描述：实现二叉树的中序遍历（左-根-右）。
思路：

• 递归：先左子树，再根，后右子树。
• 循环：用栈模拟，从根节点开始，将所有左子节点压栈，然后弹出访问，再处理右子树。

C++代码：

// 递归版本
void inorderRecursive(TreeNode* root, vector<int>& res) {
    if (!root) return;
    inorderRecursive(root->left, res); // 左子树
    res.push_back(root->val); // 访问根
    inorderRecursive(root->right, res); // 右子树
}

// 循环版本
vector<int> inorderIterative(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> stk;
    TreeNode *curr = root;
    while (curr || !stk.empty()) {
        while (curr) { // 压入所有左子节点
            stk.push(curr);
            curr = curr->left;
        }
        curr = stk.top();
        stk.pop();
        res.push_back(curr->val); // 访问根
        curr = curr->right; // 处理右子树
    }
    return res;
}

// 测试代码示例
int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    vector<int> iter = inorderIterative(root);
    for (int val : iter) cout << val << " "; // 输出: 2 1 3
    return 0;
}

😊 趣味点：循环版本像深度优先搜索的迭代实现！

---

🍂 9. 二叉树的后序遍历（递归+循环）

问题描述：实现二叉树的后序遍历（左-右-根）。
思路：

• 递归：先左子树，再右子树，后根。
• 循环：用两个栈或一个栈+反转。这里用简单方法：先做“根-右-左”的变种前序，然后反转结果。

C++代码：

// 递归版本
void postorderRecursive(TreeNode* root, vector<int>& res) {
    if (!root) return;
    postorderRecursive(root->left, res); // 左子树
    postorderRecursive(root->right, res); // 右子树
    res.push_back(root->val); // 访问根
}

// 循环版本（使用反转技巧）
vector<int> postorderIterative(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    stack<TreeNode*> stk;
    stk.push(root);
    while (!stk.empty()) {
        TreeNode* node = stk.top();
        stk.pop();
        res.push_back(node->val); // 访问根（但顺序是根-右-左）
        if (node->left) stk.push(node->left); // 先左后右
        if (node->right) stk.push(node->right);
    }
    reverse(res.begin(), res.end()); // 反转成左-右-根
    return res;
}

// 测试代码示例
int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    vector<int> iter = postorderIterative(root);
    for (int val : iter) cout << val << " "; // 输出: 2 3 1
    return 0;
}

🚀 优化：反转技巧减少栈操作，代码更简洁。

---

📊 10. 二叉树的层序遍历

问题描述：实现二叉树的层序遍历（按层输出节点）。
思路：用队列实现BFS（广度优先搜索）。从根节点开始，每层节点入队，然后出队访问，并将子节点入队。时间复杂度 $O(n)$。

C++代码：

#include <queue>
#include <vector>
using namespace std;

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> res;
    if (!root) return res;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        res.push_back(level); // 添加当前层
    }
    return res;
}

// 测试代码示例
int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    vector<vector<int>> levels = levelOrder(root);
    for (auto& level : levels) {
        for (int val : level) cout << val << " ";
        cout << endl;
    }
    // 输出: 
    // 1 
    // 2 3 
    // 4
    return 0;
}

💪 实战建议：层序遍历是BFS的基础，常用于求树的高度或最短路径。

---

结语

恭喜你完成本期数据结构篇的学习！🎉 这些题目覆盖了链表、树、搜索等核心内容，多加练习一定能掌握。如果在面试中遇到类似问题，记得先理清思路再编码哦～有问题欢迎在评论区留言，我会尽力解答。下期再见！😊

练习建议：

• 手写代码加深记忆。
• 尝试优化空间或时间复杂度。
• 刷题平台推荐：LeetCode或牛客网。

保持热情，C++上岸不是梦！💪