148. Sort List

anquan 发布于2019-08-14 17:56 / 1070人阅读

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

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

题目分析

一看到sort问题，而且时间复杂度要求又是O(n log n)，很自然地就会想到Merge sort. Merge sort数组时，pseudo code如下：

func mergesort( var a as array )
    if ( n == 1 ) return a

    var l1 as array = a[0] ... a[n/2]
    var l2 as array = a[n/2+1] ... a[n]

    l1 = mergesort( l1 )
    l2 = mergesort( l2 )

    return merge( l1, l2 )
end func

func merge( var a as array, var b as array )
    var c as array

    while ( a and b have elements )
         if ( a[0] > b[0] )
              add b[0] to the end of c
              remove b[0] from b
         else
              add a[0] to the end of c
              remove a[0] from a
    while ( a has elements )
         add a[0] to the end of c
         remove a[0] from a
    while ( b has elements )
         add b[0] to the end of c
         remove b[0] from b
    return c
end func
(Reference: http://www.algorithmist.com/i... )

这道题要求是sort linked list，所以在上面pseudo code的基础上还要进行一些额外操作：

找到List的中点，使用快慢指针法。

ListNode slow = head;
ListNode fast = head;

while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}

需要注意的是，找到中点后要把链表分成两段，即: slow.next = null;

Merge两个链表。这部分代码应该近似于merge 2 sorted lists这道题的答案。

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // find the mid point of the linked list
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode head2 = slow.next;
        slow.next = null;
        
        // if there"s only 1 element in the list, continue splitting
        ListNode list1 = null;
        ListNode list2 = null;
        if (head != head2) {
            list1 = sortList(head);
            list2 = sortList(head2);
        }
        
        // merge 2 lists
        return mergeList(list1, list2);
        
    }
    
    // merge 2 lists. reference: Merge 2 Linked List
    public ListNode mergeList(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        
        if (head2 == null) {
            return head1;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                p.next = head1;
                p = p.next;
                head1 = head1.next;
            } else {
                p.next = head2;
                p = p.next;
                head2 = head2.next;
            }
        }
        
        if (head1 != null) {
            p.next = head1;
        }
        if (head2 != null) {
            p.next = head2;
        }
        
        return dummy.next;
    }
}

复杂度分析

时间复杂度 O(n log n)
空间复杂度 O(1)

私有云云服务器 sort() sort sort()方法 sort方法

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

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

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
[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
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
MongoDB指南---16、聚合

摘要：将返回结果限制为前个。所以，聚合的结果必须要限制在以内支持的最大响应消息大小。包含字段和排除字段的规则与常规查询中的语法一致。改变字符大小写的操作，只保证对罗马字符有效。只对罗马字符组成的字符串有效。上一篇文章：MongoDB指南---15、特殊的索引和集合：地理空间索引、使用GridFS存储文件下一篇文章：MongoDB指南---17、MapReduce 如果你有数据存储在Mon...

Keagan 2019-06-26 18:06 评论0 收藏0