[LeetCode] 148. Sort List

zhoutao 发布于2019-08-19 11:17 / 3544人阅读

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;
    }
}

云服务器 GPU云服务器 LeetCode LeetCode_String leetcode_35_SearchIn sort()

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77357.html

leetcode148. Sort List

摘要：题目要求用的时间复杂度和的空间复杂度检索一个链表。那么问题就归结为如何将链表分为大小相近的两半以及如何将二者合并。之后再对折断的链表分别进行计算从而确保每一段内的元素为有序的。题目要求 Sort a linked list in O(n log n) time using constant space complexity. 用O(n log n)的时间复杂度和O(1)的空间复杂度检...

OpenDigg 2019-08-15 13:35 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
148. Sort List

摘要：题目解答对于中第二个最优解的解释根据时间复杂度的要求，很容易想到应该用的方法来做，那么就有两个步骤，分和法。题目：Sort a linked list in O(n log n) time using constant space complexity. 解答：(对于discuss中第二个最优解的解释）根据时间复杂度的要求，很容易想到应该用merge sort的方法来做，那么就有两个...

kun_jian 2019-08-14 14:09 评论0 收藏0
148. Sort List

摘要：题目分析一看到问题，而且时间复杂度要求又是，很自然地就会想到数组时，如下这道题要求是，所以在上面的基础上还要进行一些额外操作找到的中点，使用快慢指针法。需要注意的是，找到中点后要把链表分成两段，即两个链表。这部分代码应该近似于这道题的答案。 Sort a linked list in O(n log n) time using constant space complexity. 题...

anquan 2019-08-14 17:56 评论0 收藏0
[LeetCode/LintCode] Merge Intervals

摘要：方法上没太多难点，先按所有区间的起点排序，然后用和两个指针，如果有交集进行操作，否则向后移动。由于要求的，就对原数组直接进行操作了。时间复杂度是的时间。 Problem Given a collection of intervals, merge all overlapping intervals. Example Given intervals => merged intervals...

gougoujiang 2019-08-14 15:16 评论0 收藏0