Example:
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

• 模块化：截取片断链表反转再和原来的连接起来。?先走几步模块和?反转模块。
• 注意：先走几步模块需要走到被截取节点前一个，因此需要使用?辅助头节点法。

[25 Reverse Nodes in k-Group]

★★★ 📰

• 模块化：先走几步模块和反转模块。递归。翻转头几个，连接到余下的自身递归的结果。这是一种常见的一维数据递归的模板。同样在树的递归构造中，也和此有异曲同工之妙。

链表排序

[21. Merge Two Sorted Lists]

★ ? 📰

• 辅助头节点法。从辅助节点开始，贯穿一条链，串起两条链表。

[148. Sort List]

★★ ? 📰

• 归并排序，模块化。参考21的归并函数。?快慢双指针半分链表法。注意：半分链表时需要将慢指针next的属性置空切分开链表。
• 快排，?交换算法交换节点的值。?partition函数双指针同向，partition函数需要tail尾节点参数。注意的一点是链表的慢指针在结束时的位置的值应小于参考值，这样再交换参考节点（第一个)和慢指针节点的值时就方便了。non-stable。（不像数组，索引可以方便的-1+1等操作，怎么搞都好交换)。In-Place.
• 插入排序：模块化，截取节点（剩余的衔接到前面），然后从前往后比较值插入。辅助头结点法。

链表元素重排

[86. Partition List]

★★ ? 📰

• 辅助头节点法，两个辅助头节点。分拆成小于和大于等于两个链表，然后再合并，注意合并时胶水代码;

[328. Odd Even Linked List]

★★ ? 📰

• 注意这里奇数偶数指的是节点的顺序，奇数顺序的节点在前，偶数在后。?链表的间隔k抽取法，odd.next = odd.next.next; 。如果只要单独的两个链表，记得链表末尾指针置空。

[143. Reorder List]

★★ ? 📰

• L0→Ln→L1→Ln-1→L2→Ln-2→…
• ?快慢双指针半分链表。fast=head.next, slow=head, while(fast!=null&&fast.next!=null)。?合并链表模块，以较短的为基准（后半部分），这里一步要操作两个方向。

移除链表中某节点

[83. Remove Duplicates from Sorted List]

★ 📰

• 删除第二个重复节点（跳过，指针置为空)

[82. Remove Duplicates from Sorted List II]

★★ ? 📰

• 辅助头节点法（aux）。前后两指针，prev, cur, cur负责判断cur与cur.next，prev负责链接最终的结果，注意这里有个内嵌的while小循环。
• 需要注意的一点是，prev从aux开始，cur则从head开始，避免了头两个节点的无谓比较。

[19. Remove Nth Node From End of List]

★★ 📰

• 迭代，先走几步模块，?前后双指针协同走模块（一直都是每步一个节点，和快慢双指针不一样），辅助头节点法。快节点的终止条件while(fast.next != null)。

[203. Remove Linked List Elements]

★ 📰

• 迭代，辅助头节点法+提前量。

链表与环，Math

[2. Add Two Numbers]

★★ ? 📰

• ? 两链表相加，比两数组相加更容易，注意当最后进位是1时，要新建节点。

[445. Add Two Numbers II]

★★ 📰

• 模块化，反转相加再反转。

[61. Rotate List]

★★ 📰

• 迭代。左旋x：从前开始第x节点向后切断；右旋x：从后往前第x节点处向前切断（类似Find And Delete Nth From end）或等于左旋n-k。关键操作点：连接首尾成环状，后面使用先走几步模块。?求链表长度模块（1.同先走几步模块几乎一样，2. cnt=0; while(head!=null）{head = head.next}。

[141. Linked List Cycle]

★ 📰

• 快慢双指针ListNode fast = head.next, slow = head; while (fast != null && fast.next != null)…

[142. Linked List Cycle II]

★★ 📰

• 先快慢指针走到相遇，再用个其他慢指针2从头开始，两满指针走到相遇即可。

[160. Intersection of Two Linked Lists]

★ 📰

• // 思路：双指针，一个走链表1， 一个走链表2，各自走到头则从另一个链表头开始，直到会和。汇合点即第一个公共点。 双指针走了相同的距离。

Linked List And Tree

[109. Convert Sorted List to Binary Search Tree]

★★ 📰

• 递归，模块化。?有序链表转List, List转BST(递归).TreeNode n = new TreeNode(list.get(mid)); n.left = formBST(left, mid-1); n.right = formBST(mid+1, right);

其他

[138. Copy List with Random Pointer]

★★ 📰

• 迭代。?在每个节点后插入复制节点, 循环条件while(cur != null)。奇数偶数顺序链表拆分。

算法模拟：
玩游戏

========== Tree 树 ==========

树的遍历

[144. Binary Tree Preorder Traversal]

★★ ? 📰

• 递归：辅助递归函数void helper(TreeNode root, List list)
• 迭代：栈。LinkedList 模拟栈。先进个根结点。循环条件while(!stack.isEmpty())。进栈时先右节点后左节点。

[94. Binary Tree Inorder Traversal]

★★ ? 📰

• 递归：辅助递归函数void helper(TreeNode root, List list)
• 迭代：栈。LinkedList 模拟栈。循环条件TreeNode cur = root; while(!stack.isEmpty() || cur != null)。// 中序的情况比较奇怪，不需要先入根结点。因为中间过程中，根节点弹出后栈就为空了，致使循环结束，右子树无法遍历。因此还需要另外一个可以使循环继续的条件：cur 节点不断的变化。循环体中先一通向左dfs到最左节点，其间顺带入栈。弹出节点加入链表，再从弹出节点右节点继续。

[145. Binary Tree Postorder Traversal]

★★★ 📰

• 递归：辅助递归函数void helper(TreeNode root, List list)
• 迭代：栈。LinkedList 模拟栈。先进个根结点。循环条件while(!stack.isEmpty())。定义辅助指针TreeNode prev = null;先左子树各个节点入栈一波再出栈完，每次需要通过用peek来获取头部，进而加入树的下层节点(先右后左)，再右子树入栈一波再出栈完，最后出栈根节点。
  入栈条件：((cur.right != null || cur.left != null) && ((prev == null) || (cur.right != prev && cur.left != prev)))
  1. 入栈过程必要条件一： (cur.right != null || cur.left != null) cur当前节点还没有到底的过程
  2. 入栈过程必要条件二： ((prev == null) || (cur.right != prev && cur.left != prev)) 要么prev == null，意思是左子树各个节点入栈一波的过程，这个时候prev还是干净的； 要么cur.right != prev && cur.left != prev 意思是除了上一个过程外的所有入栈过程
     出栈条件：入栈条件的相反。出栈时只需简单地stack.pop(); prev = cur; 即可。

[102. Binary Tree Level Order Traversal]

★★ ? 📰

• 迭代。队列。LinkedList 模拟队列。先进个根结点。循环体中记录当前一层的size，内循环逐个poll出和加入新的下层节点（先左后右），其间将元素记录到临时List中。

[103. Binary Tree Zigzag Level Order Traversal]

★★ ? 📰

• 同102. 循环外设置判断层的奇数偶数的变量，加入每次节点的值时判断是否需要Collections.reverse(层节点值临时List)。

[107. Binary Tree Level Order Traversal II]

★★ ? 📰

• 迭代。同102， 结果使用Collection.reverse翻转即可。

[662. Maximum Width of Binary Tree]

★★ 📰

• 迭代。层次遍历，放入null空值。设置变量maxWidth存最大宽度即可。注意：1. 当一层中所有的节点都是null的时候，这一层其实已经到了“-1”层了，不能计入最大的宽度。2. 当每层的第一个或最后一个节点是null的时候，该null节点不计算其下面的两个null。

BST

[109. Convert Sorted List to Binary Search Tree]

★★ 📰

• 递归，模块化。?有序链表转List, List转BST(递归).

[108. Convert Sorted Array to Binary Search Tree]

★ ? 📰

• 模块化。有序数组转BST(递归)，同109.

[98. Validate Binary Search Tree]

★★ 📰

• 模块化+检查中序遍历的有序性
• 不必额外浪费O(n)空间存储中序遍历的整个结果，将中序遍历与检查结合起来
  • 递归的中序遍历。递归本身的性质，致使不能够在递归函数体中Fast fail/success，因此需要额外的isValid的变量存储flag。Integer inOrderMax = null; 其间first 有可能是Integer.MIN_VALUE，这是允许的情况, 此时对inOrderMax进行赋有意义初值，所以循环过程需要对inOrderMax进行非空判断。

[235. Lowest Common Ancestor of a Binary Search Tree]

★ ? 📰 【未完】

• 递归。模块化。1.同236二叉树的LCA。 2.根据root.val p.val q.val将问题范围缩小。

[199. Binary Tree Right Side View

★★ ? 📰

• 递归。右视图使用"变形的前序遍历"（先根节点，后右节点再左节点），dfs helper递归函数传depth深度，每层加1，维护全局最大深度变量，仅有当且仅当当前深度大于记录的最大深度的第一个节点，添加其值到结果列表即可。
• 迭代。队列，每层记录size()到局部变量size, 递减循环size直到size为1时加入值即可。

树的深度相关

[111. Minimum Depth of Binary Tree]

★ ? 📰

• 递归。排除掉子树的高度为0时候的情况。左右子树深度分别是left, right, 则min = left == 0 ? right+1 : right == 0 ? left+1 : (int)Math.min(left, right)+1;。

[104. Maximum Depth of Binary Tree]

★ ? 📰

• 递归。I.1 + Math.max(maxDepth(root.left), maxDepth(root.right))。II.模块化结合树的postOrder DFS, DFS递归过程中层层传递当前depth参数，每层加一，求左右过程的最大值即可。return Math.max(dfs(root.left, depth), dfs(root.right, depth))
• 迭代。队列层次遍历，每次根据队列的size()出队时记录计数器。

[559. Maximum Depth of N-ary Tree]

★ 📰

• 递归，注意foreach遍历每个子树，辅助变量求最大子树深度。

[543. Diameter of Binary Tree]

★ 📰

• 同111. 在求解深度的函数中，对直径变量进行计算（递归过程中不容易返回、传递值的，全局变量！左右子树的深度分别是l,r, 则diameter = Math.max(diameter, l+r);

[110. Balanced Binary Tree]

★ 📰

• 双层递归。模块化。首先从根节点开始，判断左右子树的高度差，大于1直接返回。然后递归左右子树各个节点。

树的操作

[101. Symmetric Tree]

★ 📰

• 递归。递归 helper(TreeNode left, TreeNode right)同时接受两个节点，分类讨论，然后return helper(left.left, right.right) && helper(left.right, right.left);
• 迭代。BFS队列实现，核心还是左右节点及其叶子节点的加入顺序。先仍进入两节点，在循环体中每次吐出两个，分别为left,right, 分类讨论，再加入left.left, right.right, left.right, right.left

[226. Invert Binary Tree]

★ ? 📰

• 递归。1. 先交换根节点下的两个左右子节点，再分别递归左右子树。2. 先递归到底，返程过程交换左右子节点。
• 迭代。层次遍历bfs。队列poll出来的节点进行左右子节点交换，后续入队操作和正常一样。

LCA (Lowest Common Ancestor)

[236. Lowest Common Ancestor of a Binary Tree]

★★ 📰

• 递归。终止条件root == null || root == p || root == q 。左子树找两节点，右子树找两节点，分别判断是否为空，得出结果。

[1123. Lowest Common Ancestor of Deepest Leaves]

★★ ? 📰

• 模块化。参考求树深度的postOrder方法，只在最深深度时记录当前的root为target，递归完后，最终的target即为所求。

最值

[1026. Maximum Difference Between Node and Ancestor]

★★ 📰

• 递归。?从根节点开始计算根节点与所有子树节点的最大差值。递归左右子树。这样所有的节点都当过一边祖先节点。

[654. Maximum Binary Tree]

★ ? 📰

• 递归。生成规则：最大值为根节点，最大值左侧在左子树，右侧右子树，如此递归。最大树的中序遍历即是给的原数组。

[998. Maximum Binary Tree II]

★★ 📰 【未完】

• 模块化。已知一个最大树和一个不重复的节点，生成一个最大树。最大树先中序遍历得到数组，插入新的节点到最后，再生成最大树。

树中PATH及其SUM

[113. Path Sum II]

★★ ? 📰

• 递归。路径（根-叶). 返回满足条件所有路径List<List>。满足的条件root.left == null && root.right == null && root.val == sum。递归的函数参数传递路径，只用一个path列表，通过在每一层递归的最后remove掉该层添加的元素，保持path不被之前的操作污染。 path.remove(path.size()-1);

[113. Path Sum]

★ 📰

• 递归。递归函数不好Fast Success, 设置类变量存储。

[113. Path Sum III]

★ 📰

• 双层递归。局部路径（任意节点间）的和为sum值的全局变量加一。满足条件root.val == sum。

生成树

[105. Construct Binary Tree from Preorder and Inorder Traversal]

★★ ? 📰

• 递归。1. 从前序数组得知的root，将中序遍历数组切分 2. 构建TreeNode, 左右递归得到左右节点。注意：左子树下前序的1…rootIndex+1,和中序的0…rootIndex个是可以对上的， 右子树前序rootIndex+1…end 对应中序rootIndex+1…end。
• 如果只是返回一个后序列表， 可以不用重建二叉树。 设置类变量： private ArrayList list = new ArrayList<>(); 递归函数无需返回值，只需在末尾 list.add(root.val); 即可

[105. Construct Binary Tree from Preorder and Inorder Traversal]

★★ ? 📰

• 递归。类似105. 左子树中序0…rootIndex对应后序0…rootIndex，右子树中序rootIndex+1…end对应后序rootIndex…end-1。

树与其他结构的转换

• tree->list (树的遍历)
• tree->linkedlist: 1. tree->list->linkedlist, 2. tree->linkedlist

[114. Flatten Binary Tree to Linked List]

★ ? 📰

• 递归。后序遍历+最后一步的操作是把左子树接到右子树上。注意需要对原左子树衔接上旧的右子树。是因为后序到最后一步操作的时候，左右两个子节点都已经知道了，便于操作。
• 迭代。把左子树移到右子树，一直深入右遍链到底，衔接上旧的右子树。如此循环此操作，每次一个root.right步骤。while(temp.right != null) { temp = temp.right; }

========== List|Array 数组列表 ==========

基本操作

https://blog.csdn.net/weixin_41615787/article/details/85115620

• 数组转列表

  • for…
  • Arrays.asList(arr) 返回基于arr的视图，长度固定，只能set，不能add/delete, 但是速度快。不考虑性能的情况下，建议new ArrayList(Arrays.asList(arr))。
  • Collections.addAll(new ArrayList(arr.lenght), arr)

• 数组转列表 (primitive type)

  • for…

  • = JDK1.8, int[] -> List: Arrays.stream(arr).boxed().collect(Collectors.toList());

• 列表转数组

  • for…
  • List -> Integer[]: list.toArray(new Integer[list.size]) ok, (Integer[])list.toArray() 是错误的，toArray()返回的是Object对象，自然不能够由高到低cast.

• 列表转数组(primitive type)

  • for…

  • = JDK1.8, List -> int[], list1.stream().mapToInt(Integer::valueOf).toArray();

• 数组基本类型和包装类型转换

  • Arrays.stream(intergerArr).mapToInt(Integer::valueOf).toArray();
  • Arrays.stream(arr).boxed().toArray(Integer[]::new);

数组排序

[912. Sort an Array]

★ ? 📰

refer: https://blog.csdn.net/fzlulee/article/details/102573566

• 快排。t O(nlgn), s O(lgn) 递归的栈空间，辅助变量
• 归并。t O(nlgn), s O(n)
• 插入。t O(n^2), s O(1)
• 选择。t O(n^2), s O(1)
• 堆排序。t O(nlgn), s O(lgn)

TOPK， Kth Largest

[215. Kth Largest Element in an Array]

★ ? 📰

• ?快速选择算法。时间O(lgn). Kth Largest即为(N-K)th Smallest。利用每次partition的轴心点分割问题，达到类似二分的效果。
• 快排然后索引。时间O(nlgn).
• 另外，参考求中位数的双堆法（大顶堆/小顶堆，始终保证两个条件：1.大顶堆的最大不大于小顶堆的最小 2. 二堆大小之差不大于1），该方法的一个缺点时要把所有的数都存起来，空间O（n）

[703. Kth Largest Element in a Stream]

★ ? 📰

• 小根优先队列。对于流，用现成的数据结构比较方便。构造函数初始化，每次加入新的元素进行头部比较。

N Sum

[Two Sum]

★ ? 📰

• hashmap，一边解决问题。t O(n), s O(n)
• 排序+双指针夹逼。t O(nlgn), s O(1)。注意在原int[]数组副本上进行排序（可用对象的Clone），因为题目要求返回的原数组元素的索引。

[3 Sum]

★★ 📰

• 排序后逐个遍历，先固定一个，在后续的数组中双指针查找。注意跳过重复的元素和初始时的优化: 如果当前的元素和前一个相同，那么直接跳过。如果后续数组中左右双指针也要考虑是否会加入和已得到的答案重复的。

关于重复

[136. Single Number]

★ 📰

• hashmap. Map.Entry<Integer, Integer> entry : map.entrySet()
• xor. 只有一个单数，其他数都是双的，双的异或掉了，剩下单数。

[268. Missing Number]

★ 📰

• 数组长度n, 元素取值范围0 ≤ a[i] ≤ n， 0…n的总和逐个减去出现的元素，最终剩下的即使missing number。
• xor. 0…n所有的异或再异或所有出现的元素，最后即所求。异或的交换律。一个数异或自身等于0. 任何数异或0仍为自身。
• 排序。

[287. Find the Duplicate Number]

★ 📰

• 要求不能修改数组。O(1) 空间。
• 参考有环链表用快慢指针找链表的环入口的方法。O(n), O(1)。巧妙！使用类似环形链表找环入口的解法的前提：n+1个数，每个数的大小1~n之间（这样确保按照元素值大小去遍历时不越界），仅一个重复值。在如此前提下，构成链式结构：nums[i] -> nums[nums[i]] -> … -> prev -> nums[prev], 起点为数组第一个元素。如果不同位置存在重复的数，那么他们各自指向的下一个数必然是相同的，即成了环。寻找重复整数即转化为找链表的环入口。

[442. Find All Duplicates in an Array]

★ ? 📰

• 元素位置调整：从前往后，逐个检查元素是否各就位或是鸠占鹊巢（原巢已被占领）。数组中所有重复的元素找出来：元素各就位调整后，找出元素与索引不匹配的元素即可。
• Note: 1) 1 ≤ a[i] ≤ n, 调整元素位置时需要-1的动作。2) 0 ≤ a[i] ≤ n-1， 调整元素位置时直接用。

[448. Find All Numbers Disappeared in an Array]

★ ? 📰(https://leetcode-cn.com/problems/find-all-numbers-disappeared-in-an-array/)

• 同442，只在最后遍历重排的数组时有区别：元素各就位调整后，找出元素与索引不匹配的索引即可。

最值，滑动窗口

[581. Shortest Unsorted Continuous Subarray]

★ 📰

• 4个循环。从前到后，找出趋势下跌后最小的，记为min；从后往前，找出趋势上升后最大的, 记为max。从前往后，找出第一个大于min的位置i, 从后往前，找出第一个小于max的位置j, i-j即为所需数组。
• 2个循环。从后往前，同时记录最小值，和大于最小值的元素，到头即可得到最小需排序窗口的左边界。同理右边。
• 注意，这种数组比较类的最值初始一般选Integer.MIN_VALUE,MAX_VALUE.

[121. Best Time to Buy and Sell Stock]

★ ? 📰

• dp. 动态规划，一遍循环。两个变量dp和curMin. dp[i]代表截止到索引i的最大利益，比较当前值和之前的最小值得差值，当前的最大利益取此差值和之前最大利益的大者。dp[i] = max(dp[i-1], cur - curMin). 优化后dp = max (dp, cur - curMin)。

[53. Maximum Subarray]

★ ? 📰

• dp. 动态规划，两个变量dp和maxSubArray，dp[i]存储截至到索引i的maxSubArray,。 转移方程为一阶. dp[i] = dp[i - 1] > 0 ? dp[i - 1] + nums[i] : nums[i]); 由于不需要dp的中间状态，可以将dp空间优化到1。dp = dp > 0 ? dp + nums[i] : nums[i]

[152. Maximum Product Subarray]

★ 📰

• dp. 动态规划。 注意要正正的正，负负得正的情况，其实需要三个dp变量，dp, curMax, curMin。注意因为题意需要的连续性，这个curMax, curMin不是累计最值，而是当前的最值，因此这里dp才是累计最值。curMax = nums[i] > 0 ? Math.max(nums[i], nums[i] * curMax) : Math.max(nums[i], nums[i] * curMin); 同理对curMin, 当心需要对curMax作暂存，以免污染。dp = Math.max(dp, max);

[239. Sliding Window Maximum]

★★★ ? 📰

• 暴力。t O(nk), s O(1). 结果数组的长度n-k+1.
• 双端队列 Deque dq = new LinkedList<>(); 存放索引值。 t O(n), s O(1). 单调递减存放的过程是从后往前，队列中小于等于当前值得都出队pollLast()；每次循环，都检查队列头部(peekFirst())的索引是否出了范围i-k。
• 类似利用队列做滑动窗口的题目：3. Longest Substring Without Repeating Characters

[150. Evaluate Reverse Polish Notation]

★★ ? 📰

• 逆波兰表达式求解，也叫后缀表达式（将运算符写在操作数之后）可以不用括号进行数学计算。
• 栈。涉及到的运算符都是双目的，运算符都在操作数后面。因此，通过一个LinkedList的栈，存操作数，每次遇到运算符将栈中的两个操作数弹出，运算后结果放入。最终栈中仅剩下结果值。

编码

[54. Spiral Matrix]

★★ ? 📰

• 编码基本能力。四个边界指针和一个剩余数的变量，不断循环直到剩余数变量为0退出。注意行列的最大最小值的动态变化。

[74. Search a 2D Matrix]

★★ ? 📰

• 二分，二维转一维。矩阵特点是每一行递增，下一行接着上一行递增。2d -> 1d, index k in 1d is matrix[k/matrix[0].length][k%matrix[0].length]。