16.链表环的入口：如果一个连表中包含环，求出环的入口节点（回归链表的地方）。
思路：1.确认环是否存在
2.找到环的入口
在开头设置两个指针，速度不一，当速度快的节点追上了速度慢的节点，则表示该链表存在环；若慢的节点直到走到链表末端都没有被快的节点追上，则表示不存在环。
当确定存在环的时候，则应该判断环入口节点的位置 。假若该环存在n个节点，则让同在链表头的两个指针，选择一个先走n步，然后两个指针同时前进，可以在入口节点相遇。
在第一部分中，两个指针相遇的节点必定在环中，则可以在判断完链表环存在之后，直接从该点开始循环遍历直到再遇见这个点，以此计算环内节点n。
17.反转链表：输入链表头节点，反转链表并且输出翻转后的链表头节点。
思路：循环，预存上一个点的地址，到下一个点处理的时候，将该地址存入该点的m_pNext地址下，同时将pPrev指向当前点，pNode指向下一个点，进入下一个循环。
鲁棒性检测：1.输入的链表头指针为nullptr时或者整个链表只有一个节点时，程序立即崩溃。
2.翻转后的链表会出现断裂
3.返回的头节点不是原始链表的尾节点
18.排序链表合并：两个同为递增序列的链表，现要求将这两个链表合并。
鲁棒性：特殊输入可能会崩溃
思路：两个链表都设置各自的链表头指针，指向的内容进行比较，更小的接入链表，前一个链表节点的m_pNext指针指向更小点，以此循环，直到其中一条链表到尾节点。若某一链表到了末尾，则另外一个链表的剩余部分直接接入目标链表。
19.树的子结构：输入两棵二叉树，判断其中一棵是否为另外一棵的子结构。
鲁棒性：边界条件（空指针）
思路：1.先找子结构的根节点 2.找整支树
a.先对当前节点进行判断，若当前结点是相同的值，则进入子结构判断函数。
b.若不是本节点不是根节点则通过递归进入左枝或右枝查找。
c.在子结构判断函数中，递归方式返回与操作的结果，即同时判断左右子节点是否为相同的。当子结构已经到底，则返回true.
20.二叉树镜像：输入一个二叉树，要求输出它的镜像。
要点：画图！！！
思路：左右节点指针呼唤。
21.二叉树对称判断：判断当前二叉树是否一样
思路：因为前序遍历是从左往右从上往下遍历，可以自定义一种同样自上而下、但是从右往左的遍历方式，如果对称，则这两种便利方式的结果会相同。对于缺少子节点的部分，空白的部分用nullptr指代。
每个节点都比对，相同数值或同为nullptr时，返回true；接下来进入递归，同时向下反向延伸（左侧节点向左右侧节点向右，左侧节点向右右侧节点向左）。
22.顺时针打印矩阵：从外向里顺时针打印矩阵中的每一个数据。
重点：当成一圈一圈来看，每次都是从左上对角开始。若跑start圈之后，start*2要刚好小于行数或列数其中之一，则代表接下来要进行最后一圈。
思路：打印时，因为往往会想到要四个方向都扫描一遍，但是当到达最后一圈时，存在只有一行、一列、甚至只有一个的情况，所以应该山区多余的扫描步骤。因此第二步需要判断终止行号大于起始行号，第三步需要判断终止列号大于起始列号，第四步则要求终止行号比起始行号至少大2.因此可以在开始圈打印之前判断一下接下来这个矩阵剩余部分的大小。
终止行/列号：rows(columns)-1-start
23.含Min()函数的栈：用min函数找到栈中最小的元素，push、pop、min的时间复杂度都是O(1)。
思路：设置辅助栈，辅助栈栈顶的最小数值和将要传入数据栈的数据进行比对，当传入数值比最小数值更小，将同样的数值直接推入辅助栈栈顶；否则，将辅助栈栈顶相同的数字推入辅助栈。这样就保留了该最小数最开始进入数据栈的位置，当数据栈中数据删除时，可以更新数据栈中的最小值。
24.栈的压入和弹出序列：输入两个证书序列，第一个表示栈的压入顺序，判断另外一个序列是否为栈的弹出序列。
思维陷阱：在压入的过程中，可以弹出。
思路：设置一个辅助栈，先比对栈顶和弹出序列的当前位置是否相同，如果相同，则弹出序列移到下一位，堆栈弹出栈顶；否则将推入序列逐位压入堆栈直到找到和该位置相等的数值，找到后弹出序列移到下一位，以此循环判断。
25.从上到下打印二叉树：同一层的从左到右打印出来。
思路：每打印一个节点，将它的子节点压入队列。
延伸讨论：将打印的二叉树分行。
思路：将下一层的节点数统计下来，也保存当前本层剩余的节点数量。当本层剩余节点数量为0的时候，输出换行，且将下一行的节点数传输给本层剩余的节点数量。
再度延伸：之字形打印
思路：双栈。轮流往两个栈里堆各自层次的子节点（刚好两层次的弹出顺序相反）。剩余思路与之前的相同。
26.二叉搜索树的后序遍历：判断输入的是不是二叉搜索树的后序遍历
二叉搜索树定义：左子树数值<根节点<右子树数值
后序遍历：先叶后干，从左至右。因此根节点就在最后一位。用该根节点将序列分隔成左子树和右子树。在子树之中同样最后一位是根节点。因此很容易看出依然是采用递归的方法来判断。
网友评论