[LeetCode hot 100] 141(142). 环形链表 题目链接 环形链表的判断在要求空间复杂度为O(1)时，需要使用Floyd判圈法来判断是否存在环。Floyd判圈法的具体讲解看这里。 具体步骤为： 快指针fast和慢指针slow指向链表头（首元结点） fast每次移动两步，slow每次移动一步 如果遇到null说明没有环，如果fast和slow相遇说明有环，进入4 其中一个指针移

[LeetCode hot 100] 23. 合并k个升序链表 题目链接 如果是合并两个链表那没得说，两个指针分别指向两个链表，每次把小的那个后移。 但是这里是k个，如果用k个指针，每次移动最小的，那么每次都需要遍历一遍找到最小的那个，时间复杂度太高了。 从k个里面找最小，这个情景很适合使用【堆】这种结构。关于堆的知识点传送门 这里使用小根堆，因为每次要获得最小的，那么小根堆取堆顶就能很轻松地完成

[LeetCode hot 100] 42. 接雨水 题目链接 这个题实在是太经典了，存在感太强了，我认为也是很考验思维的一个题，关键在于要想明白“接水”到底是怎么一回事。 这个题的难点在于，大的容器里可能有小的容器，大坑套小坑，既不能漏算也不能重复算。 这是一个坑，坑里还有小坑，还有阶梯，应该怎么算这个坑能接多少水呢？我们注意到，任何一个坑都有三个组成部分：左壁，右壁，以及中间的底。为了避免重

[LeetCode hot 100] 48. 旋转图像 题目链接 解法1：按圈旋转 这个题做的时候真是折磨，做的时候就想到像轮转数组那样可以通过多次翻转来实现旋转矩阵的效果，不过一想，好像可以一圈一圈转，也可以实现O(1)空间复杂度。具体是怎样转的呢？我画了一个图： 对于某一个环，可以分为上、右、下、左四条，旋转时上边转到右边，右边转到下边，下边转到左边，左边转到上边。如果以边为单位转，需要一个

[LeetCode hot 100] 105. 从前序与中序遍历序列构造二叉树 题目链接 这个题的关键是理解前序遍历的序列是：【根节点，【左子树】，【右子树】】，而中序遍历的序列是【【左子树】，根节点，【右子树】】。当我们拿到一个前序遍历的序列，唯一能确定的就是第一个数一定是根节点。拿到根节点后，由于没有重复值，所以可以确定中序遍历序列中根节点的位置，从而得到中序遍历的左子树区间和右子树区间，并且

[LeetCode hot 100] 128. 将有序数组转化为二叉搜索树 题目链接 这个题有点意思，乍一看挺简单，想一下就会发现有点点坑。 展开的结果是先序遍历的顺序，也就是说对于某个节点，展开后它的右子树这一串应该是根节点→左子树→右子树这个顺序，而左子树和右子树也是这样展开的。 所以对一个节点，我们首先要将左子树链到右子树中，再对左右子树都执行这个操作。这个过程的实现方法叫做Morris遍历

[LeetCode hot 100] 128. 将有序数组转化为二叉搜索树 题目链接 这个题很自然地想到要用递归，这也是构建二叉搜索树的标准步骤。每次都从当前的区间取中点作为根节点，并且分别在左右半区内寻找左孩子和右孩子（即左右半区的中点），如此递归。唯一需要注意的是我们在每次递归中都在做些什么？答：我们找到当前的节点，并调用递归来构造当前节点的左右孩子节点。只要左右孩子都没有就可以返回了，但是这

[LeetCode hot 100] 146. LRU缓存 题目链接 也是高频题目了，为了使查询get达到O(1)，自然是用哈希表来存储，但是又需要在O(1)时间完成删除（即逐出）、调整顺序等操作。这里使用双向链表比较合适，主要是因为比较方便删除。传统的单向链表想要删除还需要再遍历一遍获取前驱节点，而双向链表自带前驱节点，可以不用遍历就直接删除。 将二者结合，则哈希表应该保存<key, 链表

[LeetCode hot 100] 25. k个一组翻转链表 题目链接 好折磨的题，要想明白还真是得费一些脑筋。 我们已经做过LeetCode 206 反转链表，直到反转链表的思路是保留一个前驱节点，然后每次让后继结点的next指向前驱节点。这个题中对于每一组中的反转自然也可以这样做。 不过难点就在于局部反转后怎样和原链表接起来。思路我大致画了个图（假设k=2）： 这里有个很tricky的点，