leetcode148. Sort List

OpenDigg 发布于2019-08-15 13:35 / 2532人阅读

摘要：题目要求用的时间复杂度和的空间复杂度检索一个链表。那么问题就归结为如何将链表分为大小相近的两半以及如何将二者合并。之后再对折断的链表分别进行计算从而确保每一段内的元素为有序的。

题目要求

Sort a linked list in O(n log n) time using constant space complexity.

用O(n log n)的时间复杂度和O(1)的空间复杂度检索一个链表。

思路和代码

在给出了明确的时间复杂度和空间复杂度后，我第一个想到的就是利用divide and conquer 方法进行排序。那么问题就归结为如何将链表分为大小相近的两半以及如何将二者合并。
了解利用分治法对数组进行排序的童鞋应该知道，我们会根据数组的下标将数组取一半分别进行排序后，再将排序好的二者进行合并。
那么将链表分为大小相近的两部分则需要我们用三个指针来进行。分别是prev, slow和fast，其中fast指针每次往前跑两步，slow往前跑一步，这样确保slow指针是第二部分开头的第一个指针，而prev则是slow指针的前一个指针。prev指针是用来折断链表的。

        ListNode prev = null, slow = head, fast = head;
        while(fast!=null && fast.next!=null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;

之后再对折断的链表分别进行计算从而确保每一段内的元素为有序的。

之后我们需要将相邻的两段链表进行合并，这个就很简单了。只需要另设一个头指针，并每次比较两段的当前节点，取较小的节点加入头指针即可。

所有代码如下：

    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode prev = null, slow = head, fast = head;
        while(fast!=null && fast.next!=null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = null;
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(slow);
        return merge(l1, l2);
    }
    
    public ListNode merge(ListNode l1, ListNode l2){
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                ListNode tmp = l1.next;
                cur.next = l1;
                l1.next = null;
                l1 = tmp;
            }else{
                ListNode tmp = l2.next;
                cur.next = l2;
                l2.next = null;
                l2 = tmp;
            }
            cur = cur.next;
        }
        if(l1==null) cur.next = l2;
        else cur.next = l1;
        return dummy.next;
    }

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

混合云专线服务 Leetcod LeetCode LeetCode_String leetcode_35_SearchIn

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

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

[LeetCode] 148. Sort List

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 S...

zhoutao 2019-08-19 11:17 评论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