【Leetcode算法题】148. 排序链表

By Long Luo

148. 排序链表题目如下:

  1. 排序链表

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

进阶:
你可以在O(nlogn)O(n log n)时间复杂度和常数级空间复杂度下,对链表进行排序吗?

示例 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;
}