Leetcode 题目解析之 Sort List

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

O(n log n) 的时间复杂度，归并排序最好，因为它不会因为输入序列的基本有序而变化。

1. 首先将List分成两个
2. MergeSort(left) ，MegerSort(right)
3. LeetCode 021 Merge Two Sorted Lists

代码语言：javascript复制

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

    ListNode rt = new ListNode(0);
    ListNode h = rt;

    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            rt.next = l1;
            l1 = l1.next;
        } else {
            rt.next = l2;
            l2 = l2.next;
        }

        rt = rt.next;
    }

    if (l1 != null)
        rt.next = l1;
    else
        rt.next = l2;

    return h.next;

}

public ListNode sortList(ListNode head) {
    if (head == null)
        return null;
    if (head.next == null)
        return head;

    ListNode fast = head.next;
    ListNode slow = head;

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

    ListNode h2 = slow.next;
    slow.next = null;

    return mergeTwoLists(sortList(head), sortList(h2));

}

merge ode sort space using

0 人点赞