Problem
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
</>复制代码
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
</>复制代码
Input: -1->5->3->4->0
Output: -1->0->3->4->5
Solution
Merge Sort
Space: O(logN)
Time: O(NlogN)
</>复制代码
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head, fast = head, split = head;
while (fast != null && fast.next != null) {
split = slow;
fast = fast.next.next;
slow = slow.next;
}
split.next = null;
ListNode l1 = sortList(slow);
ListNode l2 = sortList(head);
head = merge(l1, l2);
return head;
}
private ListNode merge(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0), head = dummy;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
head.next = l1;
l1 = l1.next;
} else {
head.next = l2;
l2 = l2.next;
}
head = head.next;
}
if (l1 != null) head.next = l1;
if (l2 != null) head.next = l2;
return dummy.next;
}
}
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/77357.html
摘要:题目要求用的时间复杂度和的空间复杂度检索一个链表。那么问题就归结为如何将链表分为大小相近的两半以及如何将二者合并。之后再对折断的链表分别进行计算从而确保每一段内的元素为有序的。 题目要求 Sort a linked list in O(n log n) time using constant space complexity. 用O(n log n)的时间复杂度和O(1)的空间复杂度检...
摘要:有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像,都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归,所以空间复杂度为 ...
摘要:题目解答对于中第二个最优解的解释根据时间复杂度的要求,很容易想到应该用的方法来做,那么就有两个步骤,分和法。 题目:Sort a linked list in O(n log n) time using constant space complexity. 解答:(对于discuss中第二个最优解的解释)根据时间复杂度的要求,很容易想到应该用merge sort的方法来做,那么就有两个...
摘要:题目分析一看到问题,而且时间复杂度要求又是,很自然地就会想到数组时,如下这道题要求是,所以在上面的基础上还要进行一些额外操作找到的中点,使用快慢指针法。需要注意的是,找到中点后要把链表分成两段,即两个链表。这部分代码应该近似于这道题的答案。 Sort a linked list in O(n log n) time using constant space complexity. 题...
摘要:方法上没太多难点,先按所有区间的起点排序,然后用和两个指针,如果有交集进行操作,否则向后移动。由于要求的,就对原数组直接进行操作了。时间复杂度是的时间。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...
阅读 1717·2021-09-28 09:35
阅读 1165·2019-08-30 15:54
阅读 1697·2019-08-30 15:44
阅读 3398·2019-08-30 14:09
阅读 543·2019-08-29 14:05
阅读 2703·2019-08-28 17:53
阅读 2033·2019-08-26 13:41
阅读 1757·2019-08-26 13:26
极致性价比!云服务器续费无忧!
Tesla A100/A800、Tesla V100S等多种GPU云主机特惠2折起,不限台数,续费同价。
NVIDIA RTX 40系,高性价比推理显卡,满足AI应用场景需要。
乌兰察布+上海青浦,满足东推西训AI场景需要