https://www.nowcoder.com/exam/oj/ta?page=1&tpId=13&type=13
链表
从尾到头打印链表
- 栈
- 递归
链表反转
栈
双指针
1 -> 2 -> 3 -> 4 1 <- 2 -> 3 -> 4递归
合并两个有序链表
- 迭代
- 递归
两个链表的第一个公共结点
1 -> 2 -> 3 | 4 -> 5 |-> 6 -> 7- 栈
- 双指针：先计算长度，再找起点
- map：第一个cnt > 1的节点
链表中环的入口节点
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 ^ ^ 环 相遇（相遇时，快指针多走了1个环） 快指针：1 2 3 4 5 6 7 8 3 4 5 6 （前后长度一定相等：1 2 和 7 8） 慢指针：1 2 3 4 5 6 快指针：1 2 3 4 5 2 3 4 满指针：1 2 3 4- map：第一个cnt > 1的节点
- 快慢指针：首先，找到相遇节点；然后，慢指针接着走，新指针从头走（一次一步），再次相遇。
链表倒数第K个节点
- 双指针：前指针先走K步
- 栈
复杂链表的复制
1 -> 2 -> 3 -> 4 -> 5 3 5 * 2 * 1 _1 2 _2 3 _3 4 _4 5 _5 # 1. 复制后的新节点放在旧节点之后 3 5 * 2 * # 2. 找到旧节点的旧random节点 _3 _5 * _2 * # 3. 旧random节点的下一个节点即为新random节点 # 4. 拆分链表- 双指针
- 哈希表：hash(旧节点) = 新节点
删除链表中重复节点
输入：1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 输出：1 -> 2 -> 5- 直接删除
- 哈希表
删除链表的节点
输入：1 -> 2 -> 3 -> 4 -> 5，删除 3 输出：1 -> 2 -> 4 -> 5
树
二叉树的深度
按之字形顺序打印二叉树
输入： 8 6 10 5 7 8 11 输出：[8], [10, 6], [5, 7, 9, 11]- 队列
- 双栈
二叉搜索树的第k个节点
输入： 8 第4个节点 6 10 5 7 8 11 输出：8 (5->6->7->8)- 递归：中序遍历，左子树小于根节点
重建二叉树：输入：前序遍历结果，中序遍历结果
输入：[1,2,4,7,3,5,6,8], [4,7,2,1,5,3,8,6] 输出：{1,2,3,4,n,5,6,n,7,n,n,8} s1: 1 [2 4 7] [3 5 6 8] s2: 2 [4] [7] 3 [5] [8 6]- 递归
树的子结构：tree a是tree b的子结构
8 8 8 7 9 2 9 2 4 7- 递归
二叉树的镜像：翻转二叉树
从上往下打印二叉树：简单的层次打印
数组是否是二叉搜索树的后序遍历
递归
[1 2 3 7 9 8 5] for left < root: 左子树小于root for right < root: 右子树大于root 递归非递归：栈
二叉树某一路径的和
是否存在路径：根到叶子节点之和 = num8 22=8+8+2+4 8 7 9 2 4 7二叉树某一路径的和 II
所有路径：根节点到叶子节点之和 = sumDFS
BFS
leftpath = ... rightpath = ... rootpath = {l for l in leftpath.append(root), r for r in rightpath.append(root)}
二叉搜索树与双向链表
将二叉树转换为双向链表递归
输入： 10 6 14 4 8 12 16 输出：4 <-> 6 <-> 8 <-> 10 <-> 12 <-> 14 <-> 16
二叉树是否是平衡二叉树
平衡二叉树：左右子树高度差不超过1- 递归
二叉树的下一个节点
图
https://leetcode.cn/tag/graph/problemset/
克隆图
课程表
先转换为临界表，{未搜索，搜索中，已搜索}- DFS
- BFS
课程表II