2023.3.11

1. 不用辅助数据结构判断链表是否是回文结构，先用快慢指针找中点，从中点下一个开始反转链表。两链表挨个比可出结果。出结果后记得还原链表
2. 不用辅助数据结构将链表收尾一次相连成新链表，1题变种，只是没了比较的步骤，在还原链表的时候做链表组合
3. 给链表和一个数，按照小于数，等于数，大于数重连链表。快排partition，区别是需要准备七个变脸。最后三区相连，这里边界判断需要仔细思考
4. 链表节点中还有个r指针随机指向链表中的节点，要求将copy链表的头结点返回。先遍历链表，在元素后面插入一个它的复制。再遍历链表，连接r指针。再遍历链表，连next指针
5. 给两个链表，可能有环可能无环。重合返回第一个重合点，不重合返回null。先用快慢指针判断链表是否有环，有环返回入环点（这里有说法）。11只有一个有环，两链表不会相交。22两链表都无环，就遍历两链表找end和length。如果end不想等，两链表不想交。如果end相等，长链表先走length差步，之后两链表一起走，找第一个相交的点。33两链表都有环，如果入环点相等，参考22做升级找第一个重合点。如果入环点不想等，分两种情况。111两链表有环但不相交。222两链表相交但入环点不同，这时候返回哪个都一样。怎么判断111和222，让其中一个入环点做循环，如果循环期间碰到了另一个入环点，是222，否则是111。
6. 证明一个二叉树某节点的先序当前节点左边和后续遍历当前节点右边的数的交集是当前节点的所有父亲。先砍为什么父亲在对应的集合里。再砍为什么我的孩子都不在集合里。再砍为什么我兄弟以及我的上层节点虽然在集合里但是绝对不会重合。
7. 非递归实现二叉树先序遍历。自己压栈不用系统栈。在生产环境也是这样，程序可用的系统栈很小，但是自己建栈不受系统栈内存限制。所有这种非递归是必要的。准备一个栈，先放根节点进去，栈弹出打印，然后按右左孩子顺序压栈。一直到栈空。
8. 非递归实现二叉树后序遍历。准备两个栈，先放根节点进去，栈弹出放到另一个栈中，然后按左右孩子顺序压栈。一直到栈空。另一个栈弹出所有打印
9. 非递归实现二叉树中序遍历。首先理解原理，任何一棵树都能被所有节点极其左边界分解。中序还是左头右。那就按照这个思想先搞左再头再右。怎么搞左，根节点进栈，其左边界全部压栈。怎么搞头，最左边界的最左节点就是最先搞的头，直接弹出打