您当前所在分类目录: leetcode

[leetcode题解]147.Insertion Sort List

对单链表的排序,前几天写过一篇文章使用o(nlog(n))的时间复杂度进行排序,当时说可选的方法是利用归并或者快排对单链表进行排序,这个题目同样给定一个单链表,只不过这里要求用插入排序对其进行排序。在数组中我们使用插入排序的时候通常在寻找插入位置的时候是从后向前,这样可以同时查找并把较大的元素后移一位,然后腾出要插入的位置,但是在单链表中就不行了,首先,单链表不能逆向遍历,第二,单链表无需移动,可 …

Continue reading

[leetcode题解]148.sort list

leetcode第148题,sort list,题目给定一个单链表,要求用o(nlogn)的时间复杂度对链表进行排序,其实对于单链表的排序可以使用快排,也可以使用归并排序,对于已排序链表的合并由于比较简单,所以这里就使用归并排序实现一下。 设计了一个找链表中间节点的方法halfList,找到中间节点后将链表一分为二,左右各进行归并排序就好了,最后一个合并两个已排序链表的操作就可以了。 下面使用c+ …

Continue reading

[leetcode题解]160.Intersection of Two Linked Lists

leetcode第160题,给定两个链表的头节点,求两个链表是否相交,如果相交则返回相交的首节点,否则返回NULL。 思路是两个指针分别从头开始走,直到一个指针为NULL,这说明另一个链表比较长,而且长的这个链表剩下的节点个数正好是长度超出的节点数。这个时候把长的从头开始走,走的步数为整下的节点个数,这样短的节点从头开始,就能保证两者要走的节点数相同,也就是如果相交,那么两者分别走下去一定会在交点 …

Continue reading

[leetcode题解]203.Remove Linked List Elements

leetcode第203题,remove linked list elements,题目给定一个单链表和一个值,要求将该单链表中所有val与该给定值相等的节点删除,结果返回删除后的链表,原链表中的元素相对位置不变。 例如: Given: 1 –> 2 –> 6 –> 3 –> 4 –> 5 –> 6, val = 6 Return: 1 –> 2 –> 3 –> 4 –> 5 …

Continue reading

[leetcode题解]206-Reverse-Linked-List

简单链表逆置,这个在面试中多次要求被写,是在搞不懂这么简单的问题为什么要放在面试中,直接用头插法就可以了,下面是c++和python代码 c++代码: class Solution { public: ListNode* reverseList(ListNode* head) { ListNode *pre = new ListNode(-1); ListNode *p = head; while …

Continue reading

[leetcode题解]234.Palindrome-Linked-list

leetcode第234题,简单链表操作的题目,题目要求判断给定的单链表是否是回文的,是返回true,否则返回false。 题目比较简单,直接暴力解,通过快慢指针找到中点,然后把前半部分逆置一下,最后把前后向部分判断元素是否依次相等即可,全相等则回文,否则就不是回文。下面用了c++和python同时实现,两者的思路是完全一样的。 c++代码: class Solution { public: bo …

Continue reading

[leetcode题解]237.Delete a node in a linked list-python+c++

leetcode第237题,题目要求写一个函数实现删除链表中的一个节点,该节点以指针给出。一般链表中删除某个节点的时候我们通常是找到要删除节点的前一个节点,然后把当前节点删除掉,但是这里直接给了要删除节点的指针,题目中也说了,该节点不会是尾节点,这样我们就可以把当前节点的内容与当前节点的下一个节点的内容交换,然后删掉下一个节点就可以了。 所以代码比较简单,可以用不同的方法,以下是python和c+ …

Continue reading

[leetcode题解]328 Odd Even Linked List(python+c++)

题目给定一个包含数字的链表,要求把链表进行修改,保证奇数位置的元素按顺序排在前面,然后是偶数位置的元素一次排在后面。返回修改后的链表即可。 简单的思路就是把所有奇数位的元素摘出来按原有顺序组成一个链表even然后把所有偶数位置的元素摘出来组成一个新的链表odd,然后把odd链表链在even链表之后就可以了。这样能保证空间复杂度o(1),时间复杂度o(n)。如下为c++和python两个版本的代码。 …

Continue reading

[leetcode题解]96. Unique Binary Search Trees

如果把示例数据的顺序改一下,就可以看出规律了。 1 1 2 3 3 \ \ / \ / / 3 2 1 3 2 1 / \ / \ 2 3 1 2 比如,以 1 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 0 个元素的树, 右子树是 2 个元素的树。以 2 为根的树的个数,等于左子树的个数乘以右子树的个数,左子树是 1 个元素的树,右子树也是 1 个元素的树。依此类推。 当数组为 …

Continue reading