Leetcode 148. Sort List

作者: ShutLove | 来源:发表于2017-10-27 15:10 被阅读14次

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

    题意:常数级别的空间复杂度、O(n log n) 的时间复杂度对链表排序。
    思路:对链表进行归并排序。

    1. 待排序的链表如果是null或者只有一个节点,则直接返回。
    2. 找到链表的中间节点。
    3. 对左右两段继续递归进行排序。
    4. 将排序好的两段合并成一个链表。
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
    
        //找middle
        ListNode middle = findMiddle(head);
    
        //拆两段
        ListNode right = middle.next;
        middle.next = null;
    
        //对两段分别再进行sort
        ListNode left = sortList(head);
        right = sortList(right);
    
        //merge两段
        return merge(left, right);
    }
    
    public ListNode findMiddle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
    
        return slow;
    }
    
    public ListNode merge(ListNode left, ListNode right) {
        ListNode root = new ListNode(0);
        ListNode dummy = root;
        while (left != null || right != null) {
            if (left == null) {
                dummy.next = right;
                right = right.next;
            } else if (right == null) {
                dummy.next = left;
                left = left.next;
            } else {
                if (left.val < right.val) {
                    dummy.next = left;
                    left = left.next;
                } else {
                    dummy.next = right;
                    right = right.next;
                }
            }
            dummy = dummy.next;
        }
        return dummy.next;
    }

    相关文章

      网友评论

        本文标题:Leetcode 148. Sort List

        本文链接:https://www.haomeiwen.com/subject/iworpxtx.html