改变眼泪的理由

分类

/ 注册

全部文章（共44篇）

题解 | #删除链表中重复的结点#

//如果是未排序的链表，用桶来记录。但这题是已排序的，所以空间复杂度只要O1就够了。我们记录当前的节点，判断它与下一个节点是否相同即可。 //整体思路是简单的，但是一些细节处理比较麻烦。比如这题要求把所有重复的节点都删掉，比如1233445要求删除成125而不是12345，这要求我们把Previou...

2023-05-25

1 296

题解 | #复杂链表的复制#

//这题我有两个思路吧。如果Label能保证是不重复的话，嗯遍历就行了，只要靠Label就能找到Random指向的节点是谁。这题也确实是这样的。 //但如果不能通过Label来确定的话，就需要维护一个映射了，在构建基础链表的过程就要建立起从源链表到新链表的映射，然后回过头来遍历源链表时，就知道源链表...

2023-05-25

1 291

题解 | #链表中倒数最后k个结点#

//参考了剑指offer中记载的快慢指针法。快指针提前走k-1步。快指针抵达终点时慢指针就能到倒数第k个节点处了。例：1->2。求倒数第1个节点。提前走0步。快慢指针一起到最后一个节点。 class Solution { public: ListNode* FindKthToTail(...

2023-05-24

1 254

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

//参考了剑指offer上讲解的快慢指针法。核心思路分3步： //1.先确定有无环：快指针一次走2步，慢指针走1步，发生重逢说明有环。 //2.确定环的长度：重逢一定是在环中发生的，从重逢的位置开始，用个temp一直往前推进，直到回到这个位置，记录这个过程中走了多少步，这就是环的长度。 //3.移动...

2023-05-24

1 289

题解 | #两个链表的第一个公共结点#

class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode*p1=pHead1; ListNode *p2=pHead2; //这种做...

2023-05-20

1 212

题解 | #二叉搜索树与双向链表#

#include <tuple> class Solution { public: //官方题解里的利用一个全局变量+二叉搜索树的中序遍历本身就是有序的这个的思路挺妙的。 //思路：由于在二叉搜索树中，每一个节点的整棵左子树一定都小于这个节点。因此这个节点的prev就应该是...

2023-05-20

1 257

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

//这题由于限制了空间复杂度为O1，因此最简单粗暴的办法，把两个链表遍历一边，所有值拿出来，存进数组，排序，建一个新链表，这种思路是不行的。我们只能在原地构建一个新链表——其实就是把几个指针大家挪来挪去，你指我指你。 //思路上借鉴了之前的反转链表的题解，想象成我们建了一个新的链表，然后把旧链表上的...

2023-05-12

1 241

题解 | #反转链表#

//要用到3根指针来保证不丢。挺麻烦。题解中的双链表法，每次从原链表里摘下来的下一个节点都挂到新链表的头部，以此实现反转，这个想法很妙。 class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead-...

2023-05-12

1 248

题解 | #从尾到头打印链表#

#include <algorithm> #include <iterator> #include <vector> class Solution { public: vector<int> printListFromTailToHead(...

2023-05-12

1 218

题解 | #二叉树的下一个结点#

class Solution { public: //这题有两种做法。一种是暴力的中序遍历，把结果存储下来（应该是没有不存储结果就能提前在找到时返回的办法了。）然后去比对。但题目要求空间复杂度为O(1)，所以这种办法没法用。 //这种是分类法。我自己分了5类。 //1.是左孩子且是叶节点时（5）...

2023-05-12

1 248