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

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

By Long Luo

148. 排序链表 。

暴力 + ArrayList

思路与算法：

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

    ListNode pNode = head;

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

    Collections.sort(nodeList);

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

    return dummyNode.next;
}

123

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
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode pNode = head;

    List<ListNode> nodeList = new ArrayList<>();
    while (pNode != null) {
        nodeList.add(pNode);
        pNode = pNode.next;
    }

    nodeList.sort(Comparator.comparingInt(o -> o.val));

    ListNode dummyNode = new ListNode(-1);
    ListNode preNode = dummyNode;
    for (int i = 0; i < nodeList.size(); i++) {
        pNode = nodeList.get(i);
        preNode.next = pNode;
        pNode.next = null;
        preNode = pNode;
    }

    return dummyNode.next;
}

复杂度分析

  • 时间复杂度：\(O(n \log n + n)\)
  • 空间复杂度：\(O(n)\)

归并排序

1
2
3



复杂度分析

  • 时间复杂度：\(O(n \log n + n)\)
  • 空间复杂度：\(O(n)\)

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. 😉😃💗