题目描述

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

1 2	输入: 4->2->1->3 输出: 1->2->3->4

示例 2:

1 2	输入: -1->5->3->4->0 输出: -1->0->3->4->5

题解

小根堆

最直观想到的方法就是创建一个小根堆, 然后把每个节点都扔进去, 然后一个一个地弹出, 肯定就是排序后的链表

public ListNode sortList(ListNode head) {
    Queue<ListNode> queue = new PriorityQueue<>((v1, v2)->v1.val-v2.val);
    while (head!=null){
        queue.offer(new ListNode(head.val));
        head = head.next;
    }

    ListNode dummy = new ListNode(0);
    ListNode cur = dummy;

    while (!queue.isEmpty()){
        cur.next = queue.poll();
        cur = cur.next;
    }

    return dummy.next;
}

但是这种方法时间和空间复杂度都较差

归并排序

因为题目对时间和空间复杂度有明确的要求, 对复杂度分析想到了二分法, 进而想到了归并排序.

根据归并排序的思路, 首先要对链表进行二分. 数组的二分直接根据索引即可得到, 但是链表要用到快慢指针的操作.

将两个排序链表合并, 转化为一个排序链表, 排序的过程中, 因为不用考虑索引的改变, 比数组结构要简单一些

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

    ListNode midNode = midNode(head);
    ListNode temp = midNode.next;
    midNode.next = null;

    ListNode left = sortList(head);
    ListNode right = sortList(temp);

    return mergeTwoList(left, right);
}

private ListNode mergeTwoList(ListNode left, ListNode right) {
    ListNode head = new ListNode(0);
    ListNode cur = head;

    while (left!=null&&right!=null){
        if (left.val< right.val){
            cur.next = left;
            left = left.next;
        }else {
            cur.next = right;
            right = right.next;
        }
        cur = cur.next;
    }

    cur.next = left==null?right:left;
    return head.next;
}

private ListNode midNode(ListNode head) {
    ListNode slow = head;
    ListNode fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}