本篇难度：简答
习题一：有效的括号
题目：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例：
输入: "{[]}"
输出: true
解题思路：
本题用到了数据结构中栈的思想，规则很简单。创建一个栈stack存储左括号，碰到右括号时候，弹出stack的顶端元素看看是否与该右括号匹配。
class Solution:def isValid(self, s: str) -> bool:dic = {'{': '}', '[': ']', '(': ')', '?': '?'}# 为了防止第一个就是右括号，此时stack为空，造成stack.append(c)出错stack = ['?']for c in s:if c in dic: # 添加左括号stack.append(c)elif dic[stack.pop()] != c: # 弹出的元素与右括号不匹配return False# 长度为1是值最后所有括号都匹配，只剩'?'元素在栈中return len(stack) == 1
习题二：合并两个有序链表
题目：
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
解题思路：
调用递归，我们判断 l1 和 l2 头结点哪个更小，然后较小结点的 next 指针指向其余结点的合并结果。终止条件：当两个链表都为空时，表示我们对链表已合并完成。
因为这就是一个不断找新的链表中，最小头结点的问题，反复用一个方法，因此用递归最简单。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:if not l1: return l2 # 终止条件，直到两个链表都空if not l2: return l1if l1.val <= l2.val: # 递归调用l1.next = self.mergeTwoLists(l1.next,l2)return l1else:l2.next = self.mergeTwoLists(l1,l2.next)return l2