234.回文链表
题目描述
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
思路
1.按照原链表构建一个反向链表，如果两个链表完全相同则为回文链表
2.将原链表中的所有节点的val顺序存储在数组中后使用双指针（array[::] == array[::-1]）
3.递归
4.快慢指针
将链表的后半部分反转，然后将前半部分和后半部分进行比较。
leetcode | 232.用栈实现队列
232.用栈实现队列
题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false
说明：
你只能使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
思路
使用两个栈实现队列，一个栈作为输入栈（入队），一个对作为输出栈（出队/取队头元素）。
入队操作的实现：将元素压入输入栈
出队操作的实现：弹出输出栈栈顶元素，若输出栈为空，输入栈不为空，则将输入栈所有元素出栈并压入输出栈，接着再弹出输出栈栈顶元素。
队列判空：输入栈和输出栈同时为空时队列为空。
leetcode | 255.用两个队列实现栈
225.用队列实现栈
题目描述
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。
注意：
你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
思路
1.使用两个队列实现栈
使用两个队列实现栈的操作，其中 queue1 用于存储栈内的元素，queue2 作为入栈操作的辅助队列。
入栈操作时，首先将元素入队到 queue2，然后将 queue1 的全部元素依次出队并入队到 queue2，此时 queue2 的前端的元素即为新入栈的元素，再将 queue1 和 queue2 互换，则 queue1 的元素即为栈内的元素，queue1 的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保 queue1 的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除 queue1 的前端元素并返回即可，获得栈顶元素操作只需要获得 queue1 的前端元素并返回即可（不移除元素）。
由于 queue1 用于存储栈内的元素，判断栈是否为空时，只需要判断 queue1 是否为空即可。
2.使用一个队列实现栈
使用一个队列时，为了满足栈的特性，即最后入栈的元素最先出栈，同样需要满足队列前端的元素是最后入栈的元素。
入栈操作时，首先获得入栈前的元素个数 n，然后将元素入队到队列，再将队列中的前 n 个元素（即除了新入栈的元素之外的全部元素）依次出队并入队到队列，此时队列的前端的元素即为新入栈的元素，且队列的前端和后端分别对应栈顶和栈底。
由于每次入栈操作都确保队列的前端元素为栈顶元素，因此出栈操作和获得栈顶元素操作都可以简单实现。出栈操作只需要移除队列的前端元素并返回即可，获得栈顶元素操作只需要获得队列的前端元素并返回即可（不移除元素）。
由于队列用于存储栈内的元素，判断栈是否为空时，只需要判断队列是否为空即可。
leetcode | 206.反转链表
206.反转链表
题目描述
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
思路
1.递归
递：将大问题分解为小问题，将整个链表依次拆解直到只剩下一个节点
归：在链表只剩下一个节点时开始”归“，使用head.next.next = head,head.next = None这两行代码从后往前（从原链表的视角看）将链表中的每一个连接改为反向的
2.迭代
假设链表为 1→2→3→∅，我们想要把它改成 ∅←1←2←3。
在遍历链表时，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此必须事先存储其前一个节点。在更改引用之前，还需要存储后一个节点。最后返回新的头引用。
3.头插法
首先创建一个只有头节点的反转链表，从头到尾遍历原链表，将每次遍历到的节点按照头插法插入反转链表中，以此类推，当我们遍历完整个链表时就得到一个反转链表。
头插法：即每次都将将要插入的节点作为链表的首节点（不是头节点）
头插法代码实现：
node.next = head.next
head.next = node
leetcode | 203.删除链表元素
203.删除链表元素
题目描述
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
思路
1.递归
链表的定义具有递归的性质，因此链表题目常可以用递归的方法求解。
对于给定的链表，首先对除了头节点 head 以外的节点进行删除操作，然后判断 head 的节点值是否等于给定的 val。如果 head 的节点值等于 val，则 head 需要被删除，因此删除操作后的头节点为 head.next；如果 head 的节点值不等于 val，则 head\ 保留，因此删除操作后的头节点还是 head。
递归的终止条件是 head 为空，此时直接返回 head。当 head 不为空时，递归地进行删除操作，然后判断 head 的节点值是否等于 val 并决定是否要删除 head。
2.迭代
用 temp 表示当前节点。如果 temp 的下一个节点不为空且下一个节点的节点值等于给定的 val，则需要删除下一个节点。删除下一个节点可以通过以下做法实现：
temp.next=temp.next.next
如果 temp 的下一个节点的节点值不等于给定的 val，则保留下一个节点，将 temp 移动到下一个节点即可。
当 temp 的下一个节点为空时，链表遍历结束，此时所有节点值等于 val 的节点都被删除。
具体实现方面，由于链表的头节点 head 有可能需要被删除，因此创建哑节点 dummyHead，令 dummyHead.next=head，初始化 temp=dummyHead，然后遍历链表进行删除操作。最终返回 dummyHead.next 即为删除操作后的头节点。
leetcode | 160.相交链表
160.环形链表
题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
思路
1.哈希表
判断两个链表是否相交，可以使用哈希集合存储链表节点。
首先遍历链表 headA，并将链表 headA 中的每个节点加入哈希集合中。然后遍历链表 headB，对于遍历到的每个节点，判断该节点是否在哈希集合中：
如果当前节点不在哈希集合中，则继续遍历下一个节点；
如果当前节点在哈希集合中，则后面的节点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表 headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点，返回该节点。
如果链表 headB 中的所有节点都不在哈希集合中，则两个链表不相交，返回 null。
2.双指针
只有当链表 headA 和 headB 都不为空时，两个链表才可能相交。因此首先判断链表 headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。
当链表 headA 和 headB 都不为空时，创建两个指针 pA 和 pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：
每步操作需要同时更新指针 pA 和 pB。
如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 headA 的头节点。
当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。
leetcode | 155.最小栈
leetcode | 150.逆波兰表达式求值
150.逆波兰表达式求值
题目描述
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2”,”1”,”+”,”3”,”*”]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
思路
1.栈
遍历逆波兰表达式中的每一个字符，遇到数字则将数字入栈，遇到运算符则将栈顶的两个操作数出栈作此运算符对应的运算，再将运算结果入栈，…，以此类推，直到遍历完整个表达式，栈中剩余的元素就是表达式的结果。
2.数组模拟栈
对于一个有效的逆波兰表达式，其长度 n 一定是奇数，且操作数的个数一定比运算符的个数多 1 个，即包含 (n+1)/2 个操作数和 (n-1)/2 个运算符。考虑遇到操作数和运算符时，栈内元素个数分别会如何变化：
如果遇到操作数，则将操作数入栈，因此栈内元素增加 1 个；
如果遇到运算符，则将两个操作数出栈，然后将一个新操作数入栈，因此栈内元素先减少 2 个再增加 1 个，结果是栈内元素减少 1 个。
由此可以得到操作数和运算符与栈内元素个数变化的关系：遇到操作数时，栈内元素增加 1 个；遇到运算符时，栈内元素减少 1 个。
最坏情况下，(n+1)/2 个操作数都在表达式的前面，(n-1)/2 个运算符都在表达式的后面，此时栈内元素最多为 (n+1)/2 个。在其余情况下，栈内元素总是少于 (n+1)/2 个。因此，在任何情况下，栈内元素最多可能有 (n+1)/2 个，将数组的长度定义为 (n+1)/2 即可。
具体实现方面，创建数组 stack 模拟栈，数组下标 0 的位置对应栈底，定义 index 表示栈顶元素的下标位置，初始时栈为空，index=−1。当遇到操作数和运算符时，进行如下操作：
如果遇到操作数，则将 index 的值加 111，然后将操作数赋给 stack[index]；
如果遇到运算符，则将 index 的值减 111，此时 stack[index] 和 stack[index+1] 的元素分别是左操作数和右操作数，使用运算符对两个操作数进行运算，将运算得到的新操作数赋给 stack[index]。
整个逆波兰表达式遍历完毕之后，栈内只有一个元素，因此 index=0，此时 stack[index] 即为逆波兰表达式的值。
leetcode | 141.环形链表
141.环形链表
题目描述
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
思路
1.哈希表
最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。
具体地，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，直到我们遍历完整个链表即可。
2.快慢指针
定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。