心空之上

分类

/ 注册

全部文章（共68篇）

题解 | #链表中环的入口结点#

基本思路如果链表中有环，经过数学推导，当两者相遇时，链表从开头到相遇点的距离刚好等于环的整数倍大小，所以当两者相遇时，将快指针重置到开头，慢指针停在相遇点，然后两者开始一步一步的遍历链表，最终会同时经过环入口到达相遇点，因此再次遍历时两个指针相遇的地方就是环入口。参考参考题解 import java...

2023-08-24

0 348

题解 | #判断链表中是否有环#

快慢双指针判断链表是否有环链表是否有环一般用快慢双指针判断，快指针每次走两步，慢指针每次走一步，如果有环两个指针必然会相遇，如果没有环，快指针会先碰到null指针，所以通过判断快指针是否达到null来判断是否有环，由于快指针要走两步，所以要进行两次判断是否为null。参考参考题解 import ja...

2023-08-24

0 312

题解 | #合并k个已排序的链表#

基本思路合并k个排序好的链表，可以用归并排序，将链表数组逐步划分成左右两个部分，知道左右两个部分只有一个链表节点，此时就可以对这两个链表节点进行合并排序了，排序好的链表向上返回一个节点，再跟另一半排序好的链表节点合并排序，这样逐步向上合并返回，最终就得到一个合并整个链表数组的节点。如何确定划分到只剩...

2023-08-24

0 287

题解 | #链表中的节点每k个一组翻转#

基本思路分段反转，那么每一段都可以看成子问题，因此可以用递归解决，每一层判断当前要遍历的链表节点是否为k个，如果不是k个就直接返回原链表，如果为k个就反转当前链表，反转后的链表再接上子问题中反转完的链表的头结点，最后返回当前反转链表的头结点。初始时要遍历一遍记录一个tail指针，用于判断是否为k个节...

2023-08-23

0 377

题解 | #链表内指定区间反转#

纠正思路初始思路是用尾插法，遍历到要开始反转的第m个位置时，保存好第m个位置的前一个节点和当前节点作为反转后的最后一个节点，以便于反转后和前面以及后面的节点进行连接，但是这样当反转是从第一个节点开始时，就很难处理空指针的问题，所以还是用头插法比较好。头插法需要设置一个额外的表头节点，其next指针永...

2023-08-23

0 301

题解 | #重建二叉树#

基本思路二叉树先序遍历序列的第一个元素必然是根元素，而根据根元素在中序遍历序列中的位置就可以将序列分为左右子树，然后再递归按照左右子树序列来构建左右子树。基本思路是这样，但是不熟悉java的数组切片操作，所以还是看了题解，自己做的话可能就是for循环遍历中序序列，然后逐个将元素加入一个ArrayLi...

2023-08-22

0 248

题解 | #序列化二叉树#

基本思路序列化时采用先序遍历，遇到空节点则记录为#，并且每个节点序列化后面都加个分隔符","，这样方便序列化的字符串能够定位每个节点，str是引用地址，虽然每一层都会有一个新的引用地址的值，但是操作的都是引用地址所指向的内存的值。反序列化也采用先序遍历，先将字符串按分割符分割为节...

2023-08-22

0 272

题解 | #在二叉树中找到两个节点的最近公共祖先#

如何在二叉树中找到根节点到目标节点的路径二叉树不像二叉搜索树一样有序，因此需要递归寻找左子树和右子树，看看有没有目标节点，因此需要一个变量记录是否找到目标节点，在每一层将当前节点加入路径，如果当前节点是目标节点，则直接返回，路径数组是作为参数传入，在每一层改变的，如果当前节点不是目标节点，则到左右子...

2023-08-22

0 305

题解 | #二叉搜索树的最近公共祖先#

如何获取公共祖先？要获取公共祖先，首先要获得根节点目标节点的路径，要获取路径就需要遍历二叉树将沿途的节点加入路径数组中，而二叉搜索树是有序的，可以根据节点的大小关系选择指针遍历，而不需要循环遍历，因为路径都是从根节点出发，所以两个目标节点的最远公共祖先是根节点，最近目标节点为两个目标节点的路径中最后...

2023-08-21

0 337

题解 | #判断是不是平衡二叉树#

基本思路按照平衡二叉树的定义，需要一个函数来计算左右子树的深度，然后根据左右子树深度的差值是否不超过1判断是否为平衡二叉树，并且还要递归进入左右子树判断左右子树是否为平衡二叉树。参考参考题解 import java.util.*; /* * public class TreeNode { * ...

2023-08-21

0 267