基础面试题型100题
BM4 合并两个排序
第一个，写法按照思路顺序。
- 分清楚哪里是循环，尤其记得反向括号，可以备注。（这里的循环是list1和list2 都存在的时候）
- 创建dummy时候，需要ListNode(-1);
- 最后连接的时候，循环已经写完了。
BM3 允许反转k次链表
两次遍历获取头尾。
BM1 反转链表
可以用栈，可以用递归。
- 递归注意要设置退出节点和分割子问题。
- 非递归注意使用临时变量temp，来将cur的后一位指定。
BM5 k个排序列表
- 需要使用归并排序的方式
- 从两个链表转为多个链表，可以从归并的方式转为分治的方式
- 优先队列比较每个链表头的大小值。找到最大最小值
Queue<ListNode> pq = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
- ArrayList get()
- Queue PriorityQueue, pq.add , pq.poll() , pq.isEmpty();
C++部分
- ListNode* res = new ListNode(-1);
链表中快慢节点
由上面两个等式可以得出，f = 2nb，s = nb
故可知，两指针相遇时，慢指针已经走了nb步，已知我们要走到入口节点，需要走a + kb步，而这时s = nb只要再走a即可到达入口，我们把快指针移动到头节点，然后两个指针一步一步往后走，当它们相遇时所处的位置就是入口节点
``#第二次相遇,fast回到链表起点位：
删除倒数第n个节点
注意，这里只要两个指针，不用三个指针，删除的是first指针到头后，next的下一个指针，不是next 指针。
可以用n=2 测试条件，next是倒数第三个节点，删除的节点是倒数第二个。
BM10 两个链表的第一个公共结点
- 链一走完走链二，链二走完走链一。
- 两者相遇，相等时候，就是第一个公共节点
- 用while ！= 和 l1 ？ l2？
BM12 单链表的排序
- 递归 是先分再合。
- 当只有两个的时候，递归终止。
BM15 删除重复元素
！！！ 递归方法和迭代方法不同。
注意，递归方法，在java下，原样动c++的配置方法是不同的。
- 递归部分，可以由分割子问题来解决。默认子问题中，重复元素已经删除
- 然后在子问题到子问题的部分，判断内容。
BM31 对称二叉树
这里用了函数内直接返回一个函数的值，
思路是两个pRoot分别对应旋转前和旋转后的值。
``return` `recursion(root1->left, root2->right) && recursion(root1->right, root2->left);
这里返回的recursion值是用两个即左旋和右旋判断。
