Sort List
sort a linked list in O(n log n) time using constant space complexity.
排序,时间复杂度为n(logn),
我们知道堆排序,归并排序即使在最坏的情况下时间复杂度为n(logn)。
这里使用链表的归并排序实现。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode sortList(ListNode head) { if(head==null) return null; if(head.next==null) return head; ListNode p = head; ListNode q = head; while(q.next!=null&&q.next.next!=null) { p=p.next; q=q.next.next; } q=p.next; p.next=null; p=head; p=sortList(p); q=sortList(q); return merge(p,q); } public ListNode merge(ListNode p,ListNode q) { ListNode r = new ListNode(0); ListNode res = r; while(p!=null||q!=null) { int a,b; if(p==null) a = Integer.MAX_VALUE; else a=p.val; if(q==null) b = Integer.MAX_VALUE; else b=q.val; if(a<=b) { r.next=p; p=p.next; } if(a>b) { r.next=q; q=q.next; } r=r.next; } return res.next; } }
再来熟悉下排序的时间复杂度:
相关推荐
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest ...
list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡[LeetCode 3. Longest Substring Without Repeating Characters], N/A 2017.06.15 打卡[LeetCode 407. Trapping Rain Water II], BFS/...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
最大公共字符串leetcode leetcode 数组 链表 二叉树 位操作 判断字符串的顺序排列 给定一个字符串数组,将字谜组合在一起。 例如,给定:["eat", "tea", "tan", "ate", "nat", "bat"], public class Solution { ...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
List ) 栈 ( Stack ) 树 ( Tree ) 二叉搜索树 ( BST ) 字典树(前缀树) ( Trie ) 哈希表 ( Hash Table ) 堆 ( Heap ) 图 ( Graph ) 二分查找 ( Binary Search ) 位运算 ( Bit Manipulation ) 分治算法 ( Divide And...
list unordered_map<> 88 有序数组 合并两个vector STL vector array 26 就地删除重复元素 直接用STL sort() unique() erase()做的 122 买卖股票的最佳时机 利润最大化就是每次波谷买入波峰卖出 189 旋转数组 ...
list:链表相关题目 stack:栈相关题目 queue:队列相关题目 string:字符串处理相关题目 tree:树相关题目 divide Conquer: 分治法相关题目 dynamic Programming:动态规划 graph:图论 greedy:贪心算法 recursion:...
java lru leetcode leetcode Description My leetcode solutions. Statistics language num C++ 308 Python3 46 JavaScript 4 Java 2 SQL ...Sort ...Sort ...Sort ...Topological-Sort-拓扑排序 ...List 双向链表
leetcode下载 Leetcode 刷题记录 01. Two Sum 暴力破解时间复杂度高,使用hash表降低时间复杂度 02. Add Two Numbers 由于链表是逆置的,所以直接顺序遍历两个链表,按照加法器规则依次相加各节点,并进位 最后一组...
Arrays.sort(Object[])和Collections.sort(List)保证是稳定的。 如果需要部分排序,这对于保留原始排序很有用: 堆 对于Java,数据结构是PriorityQueue; 对于 Python,请参阅 heapq 中的函数 K 最小/最大元素来自:...
leetcode 答案 leetcode Day 1 两数之和: 1。 考虑两层嵌套循环 2。...用dictionary以及 ...List[int], ...List[int]: ...List[int], ...List[int]: ...temp.sort() i=0 j=len(nums)-1 while i<j>target: j=j-1 elif (temp
leetcode和ctf 这是什么? 这是一份skr_university的学习清单,因为太菜被抓,努力学习的一份记录 skr_learn_list 前面因为年代久远,就以周为单位,后面再以日为单位 第一周(2020.5.18-2020.5.23):Prime c++和...
leetcode LeetCodeSheet test test 记录自己Leetcode之旅 排序类(Sort)[x]: 基础知识:快速排序(Quick Sort), 归并排序(Merge Sort)的原理与代码实现。需要能讲明白代码中每一行的目的。快速排序时间复杂度...
lru缓存leetcode 力码 大批 152-最大乘积子阵列,169-多数元素,189-旋转阵列,198-房屋强盗 二分法 153-在旋转排序数组(II)中查找最小值,162-查找峰值元素 结构 155 分钟堆栈,173 二进制搜索树迭代器,HARD:...
LeetCode 解决方案。 不。 标题 笔记 标签 1 Array 2 Linked List 3 Hash Table String 4 Array Divide and Conquer Binary Search Divide and Conquer 7 Math 24 Linked List 27 Array 33 Array Binary Search 79 ...
leetcode走楼梯 LeetCoding My solutions for leetcode with explanations 【148.Sort List】 questions Sort a linked list ...sortList(ListNode* head) { } }; Requirement: Sort a linked list i
leetcode 2 sum c LeetCode LeetCode 个人题解, 解法基于C++ Content Title Difficulty Solution ...sort ...List 20. Easy stack 21. Easy merge sort 22. Medium recursion、dfs 23. Hard heap sort
List) , sum Regular Expression 、 def (函数)、 toUpperCase 、 toLowerCase 、 for...yield map , filter , & (与) distinct , filter Map , Map.getOrElse , for...yield , distinct , Conc