[Leetcode][148. 排序链表] 3种方法:暴力,自顶向下归并排序,自底向上归并排序
By Long Luo
暴力 + ArrayList
思路与算法:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24public 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;
}
1231
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26public 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(nlogn + n)\)
- 空间复杂度:\(O(n)\)
归并排序
1 |
复杂度分析
- 时间复杂度:\(O(nlogn + 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. 😉😃💗