大力推进网站集约化建设,网站 建设制作菜鸟教程,wordpress完整虚拟资源下载类源码,北京做网站商标的公司148. Sort List
问题#xff1a;要求时间度O(NlogN)O(NlogN)#xff0c;空间复杂度是常数#xff0c;实现数组排序。 思路#xff1a;之前做过linkedList的插入排序#xff0c;时间复杂度应该是O(n2)O(n2)。时间复杂度控制在nlogn 一定有二分。二分我只在数组版的list中…148. Sort List
问题要求时间度O(NlogN)O(NlogN)O(NlogN)空间复杂度是常数实现数组排序。 思路之前做过linkedList的插入排序时间复杂度应该是O(n2)O(n2)O(n^2)。时间复杂度控制在nlogn 一定有二分。二分我只在数组版的list中用过。从头和尾开始查找如此之类。这里好像有点难。 学习把列表分成两部分分别排序再合并。这个又被称为分治法。确实是这样。找到一个列表的中间位置前面的习题练习过了合并两个数组也练习过。写出递归版的代码还是没有难度的。代码。因为有栈空间的消耗所以空间复杂度不是常数而是logn。 学习2使用自底向上的策略消除递归。这种思路在23 Merge k Sorted Lists 中遇到过。不过我的问题是怎么处理合并后的各个节点。学习别人的代码吧。 解决方法1例如链表 -1-5-8-4-6。第一步要合并排序 -1,58,46null调用merge函数3次第一步合并结束后得到的链表应该是-1-5-4-8-6。第二步需要合并-1-5,4-86,null调用merge函数2次第二步合并之后得到链表-1-4-5-8。第三步需要合并-1-4-5-86调用merge函数一次得到-1-4-5-6-8。 这里考虑的代码细节是每一步中一个小的合并例如-1,5形成-1-5这样的列表5就是下一个合并后列表4-8的表头。 public ListNode sortList(ListNode head) {if (head null || head.next null) return head;int length 0;ListNode node head;while(node!null){length;node node.next;}ListNode dummy new ListNode(-1);for(int step 1;steplength; step1){ListNode tail dummy;//每一次处理的队列的队尾ListNode curr head;while(curr!null){ListNode left curr;ListNode right null;right split(left,step);//从left开始数step个节点作为第二个列表的头节点curr split(right,step);//从right开始数step个节点返回的节点用于下次合并tail merge(left,right,tail);}head dummy.next;}return dummy.next;}private ListNode split(ListNode head, int step) {for (int i 1; head ! null i step; i) {// 少走一步head head.next;}if (head null)return null;ListNode tmp head.next;head.next null;return tmp;}private ListNode merge(ListNode l1, ListNode l2, ListNode head) {ListNode cur head;while (l1 ! null l2 ! null) {if (l1.val l2.val) {cur.next l1;l1 l1.next;} else {cur.next l2;l2 l2.next;}cur cur.next;}if (l1 ! null) cur.next l1;if (l2 ! null) cur.next l2;while (cur.next ! null) {cur cur.next;}return cur;}
时间复杂度分析for循环里面split会遍历n个节点merge会遍历n个节点是O(2n)。for循环会执行logn次。所以时间复杂度O(nlogn)。
解决方法2当需要合并步长为1的两个子链表的时候合并后的结果放入队列中下次直接从队列中取子链表合并也是可以的。空间复杂度是O(n)了。 public ListNode sortList(ListNode head) {if (head null || head.next null)return head;QueueListNode queue new LinkedListListNode();ListNode node head;while (node ! null) {ListNode tmp node.next;node.next null;queue.add(node);node tmp;}while(queue.size()1){queue.add(merge(queue.poll(), queue.poll()));}return queue.poll();}public ListNode merge(ListNode l1, ListNode l2) {if (l1 null || l2 null) {return l1 null ? l2 : l1;}ListNode result new ListNode(0);ListNode preNode result;while (l1 ! null l2 ! null) {if (l1.val l2.val) {preNode.next l1;l1 l1.next;} else {preNode.next l2;l2 l2.next;}preNode preNode.next;}if (l1 ! null) {preNode.next l1;}if (l2 ! null) {preNode.next l2;}return result.next;}
代码V1 代码V2 代码V3
328 Odd Even Linked List
思路按照tag刷题尤其是从easy到hard你会发现有些难的题目是多个简单题目的组合。一个一个小问题击破了难题就解决了。 代码
109 Convert Sorted List to Binary Search Tree
思路 初看题目是没有思路的。从左到右开始构建树想什么情况下该把根节点变为左子树左子树为空的时候不能加右子树之类的….脑子里一直在想着数据结构书中讲的从非平衡树到平衡树的转换。 学习整体观察后发现链表的中间节点middle是根middle的左侧是根的左子树middle的右侧是根的右子树。 代码
138. Copy List with Random Pointer
思路深度科隆要求每个对象都要new包括每个对象的Object类型的属性。这里要处理的问题就是死循环。我的思路是迭代。 学习可以先用一层循环把所有的node new出新的对应节点再用第二层循环为每个节点赋值next和random属性。 代码
817 Linked List Components
思路遍历输入的LinkedList head如果发现当前节点node.val在G中而node.next.val不在G中那结果加1. 代码
725 Split Linked List in Parts
思路把一个linkedlist分成k份每份长度差不超过1。那就是把linkedList均分为k份。对于余数的部分分在前面的子链表中。 代码
2 Add Two Numbers
思路用两个列表表示两个整数并且是从低位到高位的顺序。例如数字是345链表是5-4-3。直接计算两个列表对应位置的和。如果满10就用carry变量保存。再加下一位的时候加上carry。网页 代码
445 Add Two Numbers II
思路把两个linkedList反转用上题的思路做。最后再将结果反转。 代码 LinkedList结束。相对来讲LinkedList是比较简单的。
