tips.md

先搭框架，写“大”步骤；再实现具体的小工具方法

边界情况

不能偷懒，列出所有可能情况的 test case const 声明的变量有没有被修改 代码中每个 cur.next.val 这种地方，有没有检测，会不会爆炸抛错

链表

• 空的
• 一个节点
• 两个节点
• 三个节点
• 与题目有关的，如重复多个相同的（尤其是首尾处），或"第一个更大的"题里，有若干比当前节点大的
• while 中有没有漏掉移动指针的步骤
• 移动节点时，注意断掉旧的链接，用新的链接。尤其是连续操作 next 的时候。

数组

• 空
• 长度为极值
• 两端边界外

引入外界辅助值，或规则

• 与数有关的，可以规定某种情况返回 -1，或正负无穷
  • 特别是涉及到比较值大小，且有负数的，用负无穷而非 0

BST 二叉搜索树

• 从定义、性质等出发考虑
• 方法上，二叉树的题考虑分治法

动态规划 Dynamic Programming

• 方案类统计的动态规划

  • 初始化的思路：
    • 一开始能把哪些东西变成 1，即哪些东西有且只有一个方案。
    • 有两个方案的，多半可以用公式套出来。

• m * n 的矩阵

  • m 是列，n 是行。画出来，m 是横，n 是竖；
  • 双循环计算内部点的时候，先 n 后 m

• 创建初始元素都为 0 的 m * n 的辅助二维数组时，一定注意，内层数组每次都要用新的副本。

排序

• 时间 O(n log n) 的常见 sort 算法，快排、归并。
• 空间 O(1) constant space 的，对于数组，只有快排，归并 O(n)；对于链表，归并也可以 O(1)。
• 两条链表 / 数组，按某种条件，组合成一个大的，想到归并排序算法

链表

• 链表单向，想要回溯，只能反转之（反转链表 while 内四行）
• 链表的递归思路
• 双指针、快慢针
  • （fast 赋值为 head or head.next 会造成最后中点的位置偏左或偏右，可带入奇数偶数个点试一试）
  • 一个走一步，一个走两步（中点）；或者 一个先走， 一个后走（倒数第 n 个）。
• 暂存链表的值，可以用数组；暂存链表节点，可以用一个 dummy node 为头结点，串一条心的链表。（space O(1)）
• 只要最后 return 的结果可能不是原来的 head（如头结点被删除等等），大都需要一个 dummy node。（dummy node 三行）
  • 进一步的，当前链表结构发生变化时，大都需要 dummy node。
    • 如 reverse 换位置等等。因为这些情况下，head 指向的头结点可能会变。
  • 构建新链表时，注意尾部的 null 别丢。
• javascript heap out of memory => 有环？