WangBa's Blog

148. SortList

LeetCode真的难系列

发布于：2020年10月26日
次浏览

148. Sort List Medium

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

Example 1:

img

1
2
Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

img

1
2
Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Example 3:

1
2
Input: head = []
Output: []

Constraints:

  • The number of nodes in the list is in the range [0, 5 * 104].
  • -105 <= Node.val <= 105

思路：

思路一：递归法

  • 归并排序
  • 找链表中点
  • 哨兵

本题是一个无序链表的排序问题，要求是空间复杂度为 O(nlogn) ，那只能想到快速排序、归并排序、堆排序，快排上通过索引的，不适合用在链表中；堆排序新建结点中；这题可采用归并排序，在 21题 中介绍了合并两个有序列表，现在只是一个无序链表，没有条件创造条件：

  • 两个链表：找到链表中点，切断
  • 有序：一个无序链表切开后，变成了两个无序链表，再对每一个链表进行递归，当只有一个结点，自然就是有序的了

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head, pre = head;
    while (fast != null && fast.next != null) {
        pre = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    pre.next = null;
    return mergeTwoLists(sortList(head), sortList(slow));
}

private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) {
            cur.next = l1;
            l1 = l1.next;
        } else {
            cur.next = l2;
            l2 = l2.next;
        }
        cur = cur.next;
    }
    if (l1 != null) cur.next = l1;
    if (l2 != null) cur.next = l2;
    return dummy.next;
}

时间复杂度：O(nlogn)

空间复杂度：O(1) 其实并不是 1 ，由于递归要调用栈

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://wangba.me/2020/10/26/148-SortList/

更新于：2020年10月26日

Leetcode

LinkedList

评论