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

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中元素个数为mmarr2arr2中元素个数为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. 😉😃💗