Sort a linked list in O(n log n) time using constant space complexity.
[分析] 将链表二分,递归排序子链表,然后merge 已排序的两子链表。
public class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
// split the list in a 2 pointer style
ListNode p = head, q = head;
while (q.next != null) {
q = q.next;
if (q.next != null) {
q = q.next;
p = p.next;
}
}
// sort 2 sublists
ListNode half1 = head, half2 = p.next;
p.next = null;
half1 = sortList(half1);
half2 = sortList(half2);
// merge 2 sublist
ListNode dummy = new ListNode(0);
p = dummy;
while (half1 != null && half2 != null) {
if (half1.val < half2.val) {
dummy.next = half1;
half1 = half1.next;
} else {
dummy.next = half2;
half2 = half2.next;
}
dummy = dummy.next;
}
if (half1 != null) {
dummy.next = half1;
}
if (half2 != null) {
dummy.next = half2;
}
return p.next;
}
}
分享到:
相关推荐
leetcode摇摆Leetcode-学习 2020/02/02 完成 Q29 & 35 2020/02/05 成品 Q58 split() function: str.split( ) means Space-separated Q69 math.sqrt() 2020/02/11 成品 Q299 Remove all rigth position element and ...
Reverse-Linked-List-II 要点: - 确定边界条件,定位到起点 - 再利用头插法对指定段的链表逆序 链表逆序之头插法,关键代码(牢记): pre.next = cur.next; cur.next = head.next; head.next = cur; ...
一.(Sort类): 350. Intersection of Two Arrays II a.首先用HashMap遍历一遍数组nums1,Key值储存数组元素,Value(初始值为1)值储存重复元素出现次数,每出现一次加1; b.用List储存nums2中与nums1开始...
List 链表 Math 数学 MySQL 数据库 Queue 队列 Recursion 递归 Sliding Window 滑动窗口 Sort 排序 Stack 栈 String 字符串 TreeNode 二叉树 UnionFind 并查集 文件: x-xxx-xxx.php 方法文件 文件前缀: e = Easy m...
1.1常数级链表排序Sort a linked list in O(n log n) time using constant space complexity.
Arrays.sort(Object[])和Collections.sort(List)保证是稳定的。 如果需要部分排序,这对于保留原始排序很有用: 堆 对于Java,数据结构是PriorityQueue; 对于 Python,请参阅 heapq 中的函数 K 最小/最大元素来自:...
copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归...
最大公共字符串leetcode leetcode 数组 链表 二叉树 位操作 判断字符串的顺序排列 给定一个字符串数组,将字谜组合在一起。 例如,给定:["eat", "tea", "tan", "ate", "nat", "bat"], public class Solution { ...
List) , sum Regular Expression 、 def (函数)、 toUpperCase 、 toLowerCase 、 for...yield map , filter , & (与) distinct , filter Map , Map.getOrElse , for...yield , distinct , Conc
list 链表 queue 队列 tree 树 interview 面试题demo blockQueueDemo 阻塞队列 casDemo cas collectionDemo 集合juc lockDemo 锁 threadDome 线程 volatileDemo cloneDemo 拷贝 java8 date lambda methodRefe ...
list.sort( key = lambda x: x[1] ) 图 = collections.defaultdict(list) heapq.heapify (列表) a = heapq.pop(队列) heapq.push(队列,ele) dq = collections.deque(list) append, appendleft, clear, copy...
迅刷leetcode 你好呀! :waving_hand: 我维护这个 repo 只是为了在面试前复习我的 DS Algo 概念。 这不是面试准备的完整指南。 参考: Gayle Laakmann McDowell破解编码面试 Eric Giguere、John Mongan 和 Noah ...
Sort & Search # Name Difficulty Solution index 1 直接插入 easy python :heart_suit: 2 简单选择排序 easy python :heart_suit: 3 冒泡排序 easy python :heart_suit: 4 希尔 easy python :heart_suit: 5 快排...
List ArrayList和LinkedList的区别和删除时注意的点 7. Proxy 静态代理和动态代理 8. Reflection java 反射 9. Sort 多种排序方法 10. Sync synchronized 和 lock 的用法 11. Thread Thread创建、ThreadLocal用法、...
丢失的最小正整数leetcode LeetCode算法归纳 我将LeetCode算法题按照标签整理了一些解题思路,下面会分别给出链接方便查看。同时,还我还贴出了一些刷题过程中...List Math Sort Stack String Tree Two Pointers Note
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
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
def minSubsequence(self, nums: List[int]) -> List[int]: nums.sort(reverse=True) # 从大到小排序 sum_ = 0 res = [] for i in range(len(nums)): sum_ += nums[i] # 累加最大数 res.append(nums[i]) if ...
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/...
reverse-linked-list-ii(Reverse a Sub-list) 141 环形链表 linked-list-cycle 142 环形链表 II linked-list-cycle-ii 143 重排链表 reorder-list 148 排序链表 sort-list 234 回文链表 palindrome-linked-list 双...