[Leetcode][148. 排序链表] 4种方法：暴力，自顶向下归并排序，自底向上归并排序

发表于 更新于 分类于 阅读次数： 本文字数： 805 阅读时长 ≈ 1 分钟

By Long Luo

Leetcode 148. 排序链表 。

方法一：

思路与算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pNode = head;
    List<Integer> list = new ArrayList<>();
    while (pNode != null) {
        list.add(pNode.val);
        pNode = pNode.next;
    }

    Collections.sort(list);
    ListNode dummyNode = new ListNode(-1);
    dummyNode.next = new ListNode(list.get(0));
    pNode = dummyNode;
    for (int i = 1; i < list.size(); i++) {
        dummyNode = dummyNode.next;
        dummyNode.next = new ListNode(list.get(i));
    }

    return pNode.next;
}

复杂度分析

  • 时间复杂度：O(m×n)O(m×n)，其中arr1arr1中元素个数为mm，arr2arr2中元素个数为nn。

  • 空间复杂度：O(1)O(1)。

方法二： 二分搜索

方法二： 二分搜索

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗