链表套路

知其然，而且要知其所以然：

为什么链表需要用到虚拟节点？因为头节点会被修改，所以备份一个虚拟节点以便于返回；

另一原因是：需要返回中间某个节点，而不是root，这时候用虚拟节点就很方便；

下面对树的操作是同一个套路；

链表的考点主要是2个：指针的修改、链表的拼接；

链表为什么总喜欢拼接？ 不必要求物理内存的连续性，而是对删除、插入的友好；

如果先处理当前节点再处理子节点，那么就是前序。如果先处理左节点，再处理当前节点，最后处理右节点，就是中序遍历。后序遍历自然是最后处理当前节点了。