By Long Luo
148. 排序链表题目如下：
- 排序链表
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在O(nlogn)时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目在范围 [0, 5 * 10^4] 内
-10^5 <= Node.val <= 10^5
方法一：暴力法
思路与算法：
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;
}
|