86. 分隔链表

解题思路：设置两个链表，分别装小于x和>=x的节点，最后将两个链表拼接。
步骤：
1.初始化两个新链表的头结点和指针节点，初始化链表的指针节点
2.遍历变量，如果是小于x，就将第一个链表的指针节点指向该节点，并更新第一个链表的指针节点；大于等于同理；最后也要更新原始链表的指针节点
3.拼接两个链表，将第一个的尾节点指向第二个链表的头节点
4.为了防止第二个链表的尾节点指向不明确，导致可能的陷入环形结构，将其指向为空
5.返回第一个链表的头节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:dummy_1 = ListNode(0) # 哑节点，用于存储所有小于x的节点dummy_2 = ListNode(0) # 哑节点，用于存储所有大于等于x的节点cur_1 = dummy_1 # 指针节点cur_2 = dummy_2cur = head# 遍历链表while cur:# 如果是小于x的节点if cur.val < x:cur_1.next = cur # 将链表1的指针指针节点指向该节点cur_1 = cur_1.next # 移动链表1的指针节点else:cur_2.next = curcur_2 = cur_2.next# 移动链表节点到下一个节点cur = cur.next# 链接两个链表，使用链表1的尾节点指向链表2的头结点cur_1.next = dummy_2.next# 确保大于或等于x的链表的尾部元素的next指针为None，避免循环cur_2.next = None# 返回链表1的头结点return dummy_1.next

237. 删除链表中的节点

解题思路

以往想到的删除方法就是把前驱节点的指针指向当前节点的后继节点。但是本题不提供头结点，只有要删除的节点。遍历不到前驱节点。

那就把自己当做前驱节点，删除后继节点（当做当前节点）。
具体做法是把后继节点复制到当前节点，删除后继节点即可。这样删除后的链表确实是删除了当前节点。

步骤

1.把后继节点的值复制到当前节点
2.把当前节点的指针指向后继节点的下一个节点

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def deleteNode(self, node):""":type node: ListNode:rtype: void Do not return anything, modify node in-place instead."""# 修改node的值为后继节点的值node.val = node.next.val# 将node的指针指向后继节点的下一个节点node.next = node.next.next# 这样使得node整个节点更新为其后继节点

138. 复制带随机指针的链表

解题思路

要求是全新的链表，如果是普通链表，直接遍历，过程中创建新节点，前驱节点指向当前节点即可。
但是本题的节点加了个随机指针，既然随机，如果在遍历过程中新增节点，随机指针没地方指啊。

因此采用哈希表+二次遍历的方法。
建立键为原链表节点，值为新链表节点的哈希表。新链表节点的随机指针取默认值。
在二次遍历的时候，根据原链表节点的随机指针指向，更新新链表节点的随机指针。

步骤

1.初始化哈希表，指针节点
2.一次遍历链表，填充哈希表
3.重置指针节点到头节点，二次遍历，修改新节点的指针和随机指针。中间要考虑到随机指针指向空，会导致字典查不到该键对应的值。
4.返回新链表的头节点（哈希表对应的旧链表的头节点的值）

"""
# Definition for a Node.
class Node:def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):self.val = int(x)self.next = nextself.random = random
"""class Solution:def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':if not head: return # 哈希表存储旧新节点的映射_dict = {}cur = head# 第一次遍历链表，构建旧新节点的映射while cur:node = Node(x=cur.val) # 构建新节点（只能建立值）_dict[cur] = node # 将旧节点作为键，新节点作为值cur = cur.next# 重置指针节点，进行第二次遍历cur = head# 构建新链表节点的指针while cur:# 构建普通指向if cur.next: # 防止字典键为空_dict[cur].next = _dict[cur.next]# 随机指针if cur.random: # 考虑到cur.random为空时，出现字典里找不到的情况_dict[cur].random = _dict[cur.random]# 移动指针cur = cur.next# 返回头节点return _dict[head]

20. 有效的括号

解题思路

有效：次数和顺序都要满足要求。
使用栈，先进后出。
遍历字符串，将开放括号入栈，遇到闭合括号的时候弹出栈顶元素，如果是满足要求的，那栈顶元素一定和闭合括号是一对。如果不是，那就直接返回false。
最后也要检查有没有足够的闭合括号，如果栈里还剩的有开放括号，那肯定也是不行的。

步骤

1.初始化栈，哈希表（开放：闭合括号），手动加上特殊字符（防止第一词遍历就遇到闭合括号，空栈弹出报错）
2.遍历字符串，遇见开放括号就入栈；遇见闭合括号就弹出栈顶元素，并进行比较，能否消消乐。
3.遍历完成后检查是否栈中还有剩余的开放括号。

class Solution:def isValid(self, s: str) -> bool:# 初始化栈，哈希表：开放：闭合括号stack = ['#']_dict = {'(': ')', '[': ']', '{': '}', '#': '#'}# 遍历，开放括号入栈，闭合括号就出栈for i in s:if i in '([{': # 入栈stack.append(i)else: # 闭合括号，弹出栈顶元素temp = stack.pop()# 检查弹出元素的对应闭合括号是不是当前遍历到的if _dict[temp] != i:return False# 为防止第一次就遇到闭合括号，导致弹出元素失败（栈为空），先加了个特殊字符# 最后判断如果都消消乐完了，就还剩个手动添加的特殊字符了return len(stack) == 1

155. 最小栈

解题思路

使用两个栈完成，一个主栈，一个辅助栈（每个阶段的最小值放在栈顶）
入栈的时候，主栈直接入；辅助栈需要判断：如果辅助栈为空，或者小于等于栈顶元素，就能入栈。
出栈的时候，主栈直接出；辅助栈依然要判断：如果主栈出的元素等于栈顶元素，那么就要出栈。
取栈顶元素和最小元素就分别取主栈和辅助栈的栈顶元素（最后一个元素）即可

步骤

1.初始化主栈和辅助栈
2.入栈：主栈直接入；辅助栈进行判断：为空或者小于等于栈顶元素。注意不要使用pop，不然就把栈顶元素弹出了，使用索引
3.出栈：主栈直接出；辅助栈判断：主栈出的元素是不是等于其栈顶元素。
4.取值，直接按索引取。

class MinStack:def __init__(self):# 初始化self.stack = []self.min_stack = []def push(self, val: int) -> None:# 主栈入栈self.stack.append(val)# 如果辅助栈为空，或者元素小于等于辅助栈栈顶元素，就入栈if not self.min_stack or val <= self.min_stack[-1]:self.min_stack.append(val)def pop(self) -> None:value = self.stack.pop()# 根据值决定是否弹出辅助栈栈顶元素if value == self.min_stack[-1]:self.min_stack.pop()def top(self) -> int:# 返回栈顶元素return self.stack[-1]def getMin(self) -> int:# 返回最小元素return self.min_stack[-1]