力扣题解8/17

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

接着道题需要运用栈的知识，建立一个栈来存储左括号，在当遍历到右括号时再将栈中的·左括号拿出来匹配，如果不匹配则返回false，当遍历到最后一个括号仍能匹配且栈中的左括号全部出栈时则表明这串括号符合要求，返回true；

同时要想使符号串符合要求则每种括号必是成对出现，那么当符号串长度为奇数是可以直接返回false；

判断括号是否匹配使用一种巧妙的方法设立一个函数当遇到右括号是返回相应的左括号再和栈中的左括号对比是否相等就可以实现左右括号的匹配。

具体代码如下

char pairs(char a) {
    if (a == '}') return '{';
    if (a == ']') return '[';
    if (a == ')') return '(';
    return 0;
}
 
bool isValid(char* s) {
    int n = strlen(s);
    if (n % 2 == 1) {
        return false;
    }
    int stk[n + 1], top = 0;
    for (int i = 0; i < n; i++) {
        char ch = pairs(s[i]);
        if (ch) {
            if (top == 0 || stk[top - 1] != ch) {
                return false;
            }
            top--;
        } else {
            stk[top++] = s[i];
        }
    }
    return top == 0;
}

21. 合并两个有序链表

难度简单2612

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

 这道题就是对链表知识的运用，建立一个新的链表，对比l1和l2的值，那个小就优先加入到新链表中，当其中一个链表到末尾后直接将另一个链表剩下的部分加到新链表后面，知道l1和l2都到末尾后输出新链表

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    struct ListNode* cur = dummy;
    while(list1 && list2)
    {
        if(list1->val < list2->val)
        {
            cur->next = list1;
            list1 = list1->next;
            cur = cur->next;
        }
        else
        {
            cur->next = list2;
            list2 = list2->next;
            cur = cur->next;
        }
    }
    if(list1)
        cur->next = list1;
    else
        cur->next = list2;
        return dummy->next;
}