（一）JZ36 二叉搜索树与双向链表（经典题目）
首先，我们第一题给大家讲述的是关于一道 二叉搜索树与双向链表 的问题。首先，拿到题我们还是先从题干入手，理解好题意才能更好进行解题操作。
题目如下：
输入描述：
二叉树的根节点
返回值描述：
双向链表的其中一个头节点。
示例1
输入：{10,6,14,4,8,12,16} 返回值：From left to right are:4,6,8,10,12,14,16;From right to left are:16,14,12,10,8,6,4; 说明：输入题面图中二叉树，输出的时候将双向链表的头节点返回即可。
示例2
输入：{5,4,#,3,#,2,#,1} 返回值： From left to right are:1,2,3,4,5;From right to left are:5,4,3,2,1; 说明： 5 / 4 / 3 / 2 / 1 树的形状如上图
1、题意分析
首先我们第一看到这个题目就会发现，如果我们对其进行中序遍历，则得到的结果为【4,6,8,10,12,14,16】，此时就符合我们题干的要求，再次把它转化为双向链表即可。
注意：
- 此时很多小伙伴就会想到我们直接对这棵树进行中序遍历，最后尾插即可。其实这样是不行的，因为题目告诉我们只能在原树中进行操作，不能创建新结点、因此这种思想是不行的。
2、思路讲解
首先，我们先将一下二叉搜索数的一些概念帮助大家做题：
它要么是一棵空树，要么就具有下列性质的二叉树：
- 1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 3. 它的左、右子树也分别为二叉排序树。
思路一：
此时可能会有小伙伴这样去想，那我们可不可以用个容器进行操作呢？
- step1：首先我们先定义一个 vector 用来存放结点；
- step2：紧接着进行中序遍历，将结点放进vector 中，最后再改链接关系即可。
这其实是一个非常棒的思路，而且 牛客 应该对空间复杂度也没有进行很大的限制，最多限制其时间复杂度。因此，这种方法理论上应该是可行的（我在这里就不去实现了，大家有兴趣可以进行尝试）
思路二：
step1：首先我们需要确定一点，那就是这道题肯定与中序有关。是通过改变为中序这样的关系来进行实现的；
step2：我们先中序遍历这棵树，并记录一个前驱结点（最开始前驱为空）。那我们如何记录一个前驱结点呢？
- 在 cur 往下走之前我先给 前驱结点，此时就变为前驱了，在递归往下走；
- 此时一个结点的左无论如何都是指向前驱的；
注意：
此时又出现一个问题，我的左即前驱可以解决，但是我的 右 该如何解决呢？
- 我们不能用 ->next 的方法，因为我们还没遍历过去呢？怎么知道后继在哪呢？我们只知道前驱在哪。
step3：此时我们对于可以这样去考虑：
- 在当前位置我可以改我的前驱，却改不了我的后继；
- 但是我可以在下一步在动手去改，即我确定上一步的下一步一定是我；
- 因此关键在于我们先把前驱弄完了，通过前驱再去修改后继即可
cur->left=prev; prev->right=cur;
注意：
这个题目的思想其实和二叉树的线索化非常相似。在这里简单提一句：
- 二叉树的线索化就是把那些空指针利用起来，找它的前驱和后继，这样的话可以做一个迭代遍历的操作。
3、代码演示
class Solution { public: void InorderConvert(TreeNode* cur,TreeNode* &prev) { if(cur == nullptr) return; InorderConvert(cur->left,prev); cur->left=prev; if(prev) prev->right=cur; prev=cur; InorderConvert(cur->right,prev); } TreeNode* Convert(TreeNode* pRootOfTree) { TreeNode* prev=nullptr; InorderConvert(pRootOfTree,prev); TreeNode* head=pRootOfTree; while(head && head->left) { head=head->left; } return head; } };
4、最终结果
我们提交代码，最终程序执行成功！！！
（二）BM6 判断链表中是否有环
题目如下：
- 示例1
输入：{3,2,0,-4},1 返回值：true 说明： 第一部分{3,2,0,-4}代表一个链表，第二部分的1表示，-4到位置1（注：头结点为位置0），即-4->2存在一个链接，组成传入的head为一个带环的链表，返回true
- 示例2
输入：{1},-1 返回值：false 说明： 第一部分{1}代表一个链表，-1代表无环，组成传入head为一个无环的单链表，返回false
- 示例3
输入：{-1,-7,7,-4,19,6,-9,-5,-2,-5},6 返回值：true
1、题意分析
- 首先我们简单的分析一下这道题目，其实很简单，对于给出的第一个部分即表示我们要操作的链表，第二部分的数字如果为 -1 则表示此链表没有环。
- 如果为其他的数字则表示链表末尾到数字对于的下标处的结点之间形成环。
2、思路讲解
- step1：使用快慢指针的思想，即快指针买次走两步，慢指针每次走一步；
- step2：因为快指针会先进入环，慢指针会后进入环。一旦快指针入了环之后就会一直在环里进行循环，因此如果存在环的话，那么快慢指针经过不断的遍历之后一定会在其中的某一点处相遇。一旦相遇返回 true 即可
- step3：相反的，如果不存在环，那么快慢指针就一定不会相遇。此时只需返回 FALSE 即可。
- step4：最后就是对于代码的处理了，具体如下。
3、代码演示
class Solution { public: bool hasCycle(ListNode *head) { //首先判断链表为空的情况 if(head == nullptr || head->next == nullptr) return false; //接下来设置快慢指针 ListNode* fast = head->next; ListNode* slow = head; //如果两指针没相遇就继续 while(slow != fast) { //无环情况判断 if(fast==nullptr || fast->next == nullptr) return false; //快指针移动两步 fast = fast->next->next; //慢指针移动一步 slow = slow->next; } return true; } };
4、最终结果
（三）JZ23 链表中环的入口结点
题目如下：
- 示例1
输入：{1,2},{3,4,5} 返回值：3 说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3
- 示例2
输入：{1},{} 返回值："null" 说明：没有环，返回对应编程语言的空结点，后台程序会打印"null"
- 示例3
输入：{},{2} 返回值：2 说明：环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2
1、题意分析
- 这道题跟上述的题目有很多类似之处，因此在做这道题之前我先给大家给出了一道判断是否存在环的题目，帮助大家更好的理解这道题。
- 这道题的整体思路跟上述的其实差不多，上述我们是判断有没有环，这里我们则可以先判断是否有环，紧接着再去看链表的入环结点在哪！
2、思路讲解
本题的主要步奏其实就是两步：
- 第一步就是判断链表是否有环。
- 第二步如果有环，则在有环的链表中找到环的入口返回即可
具体步奏如下：
step1：首先还是使用快慢指针的思想，即快指针买次走两步，慢指针每次走一步，此时会产生两种情况：
- ①无环：当快指针走向链表末端的时候，此时直接返回 null即可
- ②有环：当有环时，此时当快指针进入环之后依旧还是在环里一直循环遍历的，此时当 fast==slow 的时候，两指针在这时首次相遇。此时，我们需要把 fast 指针指向头结点，紧接着两指针各自在走一步步的走，当走到两指针再次相遇时 ，此时所指向的结点即为我们的入环结点，返回即可。
我以如下图示给大家分析上述:
step2：分析原因
- ①如上图所示，我们假设环外的长度为m ，此时当slow进入环之后，需要再走 n步指针才能与 fast 指针相遇。因为快指针比慢指针走得快，因此假设两指针相遇之前，fast 指针已经走了 a圈，此时 fast 指针走过的距离有 【m+a(n+k)+n】; slow 指针走过的距离为 【m+n】
- ②此时，我们可以得出一个公式结论。因为 fast 一次走两步， slow 一次走一步 ，因此我们得出以下公式 m+a(n+k)+n=2*(m+n)
- ③根据上面的公式，我们可以推倒出 m=(a-1)*(n+k)+k
- ④上面的式子含义即为从链表头部到入环结点距离 等于 从相遇点到入环结点的距离+（a-1）倍的圈长
3、代码演示
class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { //快慢双指针 ListNode* fast = pHead; ListNode* slow = pHead; //如果没环快指针会先到链表尾 while(fast != nullptr && fast->next != nullptr) { //快指针移动两步 fast = fast->next->next; //慢指针移动一步 slow = slow->next; //相遇则有环 if(fast == slow) { //此时从首结点开始向后遍历如果与慢指针相遇则当前结点为入环结点 while(pHead != slow) { slow = slow->next; pHead = pHead->next; } return slow; } } return nullptr; } };
4、最终结果
（四 ）HJ43 迷宫问题
题目如下：
- 示例1
输入： 5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 输出： (0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)
- 示例2
输入： 5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 输出： (0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4)
1、题意分析
首先，开始时我们并不知道该结点可以往哪走，上下左右四个方向我们并不知道哪条是可行的。因此不难看出本题我们需要用到 “回溯法”去进行解决。
其次，通过我们的分析也不难发现。对于路径的选择是不确定的。对于题意是找到最短的路径，因此我们还要对路径进行最优判断。
2、思路讲解
step1：首先我们可以从入口处开始进行递归搜索，每次进入一个点，将其加入临时路径数组中；
step2：紧接着我们判断是否进入到了出口处；
step3：如果没有依次搜索当前位置的上、下、左、右四个方向的点，如果搜索的这个点可以进入则路径进入，如果四个方向都没有可以走的路表示该结点走不通，此时需要恢复原场面，回溯——删去路径最后一个，重置该位为0.
step4：找到横纵坐标都等于矩阵最后一位则表示找到路径，复制现有路径然后返回。
3、代码演示
#include <iostream> #include<vector> using namespace std; int ROW, Cal; vector<vector<int>>arry; vector<vector<int>>Path_tmp; vector<vector<int>>Path_way; void Mazeway(int i, int j) { arry[i][j] = 1; Path_tmp.push_back({ i, j }); //判断是否到达出口 if (i == ROW - 1 && j == Cal - 1) { if (Path_way.empty() || Path_way.size() > Path_tmp.size()) Path_way = Path_tmp; } //向右走 if (j + 1 < Cal && arry[i][j + 1] == 0) { Mazeway(i, j + 1); } //向左走 if (j - 1 >= 0 && arry[i][j - 1] == 0) { Mazeway(i, j - 1); } //向下走 if (i - 1 >= 0 && arry[i - 1][j] == 0) { Mazeway(i - 1, j ); } //向上走 if (i + 1 < ROW && arry[i + 1][j] == 0) { Mazeway(i + 1, j); } //该结点走不通，此时需要恢复原场面 arry[i][j] = 0; //从路径中删除该节点 Path_tmp.pop_back(); } int main() { while (cin >> ROW >> Cal) { arry = vector<vector<int>>(ROW, vector<int>(Cal, 0)); Path_tmp.clear(); Path_way.clear(); for (int i = 0; i < ROW; ++i) { for (int j = 0; j < Cal; ++j) { cin >> arry[i][j]; } } Mazeway(0, 0); for (int i = 0; i < Path_way.size(); ++i) { cout << "(" << Path_way[i][0] << "," << Path_way[i][1] << ")" << endl; } } return 0; } // 64 位输出请用 printf("%lld")
4、最终结果
我们提交代码，最终程序执行成功！！！
到此，便是今天刷题的所有解答啦！希望对大家有所帮助。非常感谢您的阅读！！！
