Day 10。
不知不觉，已经坚持到第十天了。
今天两道题分别是 有效括号 和 合并两个有序链表，一个偏 栈结构匹配，一个偏 链表基础操作。

今天的关键词：栈、匹配、虚拟头结点、有序合并。

🧠 LeetCode 20 – Valid Parentheses

💡 思路总结

这题是非常经典的栈题。

题目要求判断括号字符串是否有效，本质就是：

  • 左括号先入栈
  • 遇到右括号时，检查栈顶是否能和它配对
  • 如果能配对，就弹出
  • 如果不能配对，直接返回 false

最后如果栈为空，说明所有括号都成功匹配。

💻 代码实现

#include <stack>

class Solution {
public:
    bool isValid(string s) {
        stack<char> sta;

        for(char c : s){

            if(c == '(' || c == '{' || c == '['){
                sta.push(c);
            }
            else{

                if(sta.empty()) return false;

                if(sta.top() == '(' && c == ')') sta.pop();
                else if(sta.top() == '{' && c == '}') sta.pop();
                else if(sta.top() == '[' && c == ']') sta.pop();
                else return false;
            }
        }

        return sta.empty();
    }
};

📌 知识点总结

1️⃣ 为什么要用栈

因为括号匹配天然符合：

后进先出

比如：

{ [ ( ) ] }

最后进来的左括号，必须最先被匹配掉。
这就是栈最适合的地方。

2️⃣ 核心逻辑

这题本质只有两步：

  • 左括号入栈
  • 右括号检查栈顶并匹配

所以这题其实是一个非常标准的“栈模拟题”。

3️⃣ sta.empty() 很关键

当遇到右括号时，如果栈已经空了：

if(sta.empty()) return false;

说明没有左括号和它匹配，字符串一定无效。

这个边界判断不能少。

4️⃣ 最后还要检查栈是否为空

有些字符串看起来中途没出错，但最后可能还有多余左括号，比如：

"((("

所以最后必须：

return sta.empty();

只有栈真正空了，才说明匹配完全成功。

🔗 LeetCode 21 – Merge Two Sorted Lists

💡 思路总结

这题要求把两个有序链表合并成一个新的有序链表。

核心思路和“合并两个有序数组”很像：

  • 两个指针分别指向两个链表当前节点
  • 每次取值更小的那个接到结果链表后面
  • 某一边走完后，把另一边剩余部分直接接上

这题本质上就是：

双指针 + 链表模拟

💻 代码实现

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (list1 == NULL && list2 == NULL) return NULL;
        else if (list1 == NULL && list2 != NULL) return list2;
        else if (list1 != NULL && list2 == NULL) return list1;
        else {
            ListNode* curr_1 = list1;
            ListNode* curr_2 = list2;
            ListNode* dump = new ListNode(0);
            ListNode* curr = dump;

            while (curr_1 != NULL && curr_2 != NULL) {
                if (curr_1->val <= curr_2->val) {
                    curr->next = curr_1;
                    curr = curr->next;
                    curr_1 = curr_1->next;
                } else {
                    curr->next = curr_2;
                    curr = curr->next;
                    curr_2 = curr_2->next;
                }
            }

            if (curr_1 != NULL) {
                curr->next = curr_1;
            }
            if (curr_2 != NULL) {
                curr->next = curr_2;
            }

            ListNode* result = dump->next;
            return result;
        }
    }
};

📌 知识点总结

1️⃣ 有序链表合并的核心

因为两个链表本身就是有序的，所以不需要重新排序，只需要不断比较当前节点值：

  • 谁小，谁先接上
  • 然后对应指针后移

这就是典型的“有序结构合并”思想。

2️⃣ 虚拟头结点太好用了

你这里用了：

ListNode* dump = new ListNode(0);

这就是虚拟头结点。
它的作用还是老朋友那一套：

  • 统一处理头节点
  • 避免第一次插入时单独分类讨论
  • 让代码更整齐

链表题里，虚拟头结点几乎永远值得优先考虑。

3️⃣ 收尾处理不能漏

当其中一个链表走完后，另一个链表剩余部分一定还是有序的，所以可以直接接上：

if (curr_1 != NULL) {
    curr->next = curr_1;
}
if (curr_2 != NULL) {
    curr->next = curr_2;
}

这一步很经典，也很重要。

4️⃣ 一个可以优化的小点

你这里申请了 dump，最后返回了：

ListNode* result = dump->next;
return result;

逻辑没问题。
不过如果想更规范一点，可以顺手把 dump 释放掉，避免内存泄漏。

当然在 LeetCode 里一般问题不大，但写博客时可以顺带记一下这个习惯。

🧩 今日总结

题目核心思想
LeetCode 20栈 + 括号匹配
LeetCode 21双指针 + 链表有序合并

今天两题都属于特别经典的基础题：

  • 20 是栈题模板
  • 21 是链表题模板

这种题的价值很高，因为它们会反复以变形形式出现。

🧠 今日收获

今天最值得记住的两个模型：

1. 括号匹配类问题

遇到这种“成对匹配、顺序相关”的题，优先想：

  • 栈
  • 后进先出
  • 栈顶匹配

2. 有序链表合并类问题

遇到两个有序结构合并时，优先想：

  • 双指针
  • 谁小接谁
  • 剩余部分直接拼接

这个模型以后在归并排序、合并 K 个链表里还会继续出现。

💬 写给自己的话

Day 10 了。

十天，其实已经很不容易了。
很多事情最难的不是开始，而是连续做十天。

更重要的是，你现在已经不是单纯在“刷题打卡”了，
而是在慢慢认识这些高频套路：

  • 栈怎么用
  • 链表怎么处理
  • 双指针什么时候上
  • 虚拟头结点什么时候加

这就是积累。

别急着追求做多难的题，
先把这些经典题真正做熟。
等这些基础套路都变成你的直觉，后面很多题都会顺起来。

继续坚持。
第 10 天只是一个小节点，不是终点。

阿玉，Day 10，继续冲。你已经比十天前强了很多。

—— 刷题第 10 天