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

有效字符串需满足：

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

示例 1：

输入：s = “()”
输出：true
示例 2：

输入：s = “()[]{}”
输出：true
示例 3：

输入：s = “(]”
输出：false
示例 4：

输入：s = “([)]”
输出：false
示例 5：

输入：s = “{[]}”
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

思路：

• 由于每种类型的括号都有与之单一对应的另一边，符合key： value形式， 因此可以用Map来存储
• 使用栈来完成对应操作，当为左括号那么直接进栈；如果为右括号，那么判断是否有栈顶是否有与之对应的左括号，如果没有直接返回false，如果此时栈为空，那么也直接返回false

• 由于判断是否为右括号在前，那么就不存在右括号单独进栈的问题

  class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if(n%2==1)return false;
        Map<Character,Character> map = new HashMap<>(){{
            put(')','(');
            put('}','{');
            put(']','[');
        }};
        Deque<Character> stack = new LinkedList<>();
        for(int i=0;i<n;i++){
            char ch = s.charAt(i);
            if(map.containsKey(ch)){
                if(stack.isEmpty()||stack.peek()!=map.get(ch)){
                    return false;
                } else{
                    stack.pop();
                }
            }else{
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
  }

• 时间复杂度：O(n)，其中 n 是字符串 s 的长度。

• 空间复杂度：O(n+∣Σ∣)，其中 Σ 表示字符集，本题中字符串只包含 6 种括号，∣Σ∣=6。栈中的字符数量为 O(n)，而哈希表使用的空间为 O(∣Σ∣)，相加即可得到总空间复杂度。

2. 合并两个有序链表

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

示例 1：

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

输入：l1 = [], l2 = []
输出：[]
示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

思路：

• 首先排除特殊情况，即：当链表l1为空，或者l2为空

• 判断两个节点中对应的值，小的那个节点指向 递归判断的小的那个节点的下一个节点与大的那个节点的值，并返回进行指向的那个节点。即： 当l1值小于l2，那么l1指向l2 与l1下一个节点即（l1.next）的判断后的节点。以此递归。

  class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        } else if(l2 == null){
            return l1;
        } else if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        } else{
            l2.next = mergeTwoLists(l2.next,l1);
            return l2;
        }    
    }
  }

  复杂度：

• 时间复杂度：O(n+m)，其中 nn 和 m 分别为两个链表的长度。因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），函数 mergeTwoList 至多只会递归调用每个节点一次。因此，时间复杂度取决于合并后的链表长度，即 O(n+m)。

• 空间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。结束递归调用时 mergeTwoLists 函数最多调用n+m 次，因此空间复杂度为 O(n+m)。