题目
给你链表的头结点 head
,请将其按 升序 排列并返回 排序后的链表 。
示例 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
进阶:你可以在 O(n log n)
时间复杂度和常数级空间复杂度下,对链表进行排序吗?
解题
方法一:哈希表
思路
遍历链表转为集合,排序后转回链表
代码
class Solution {
public ListNode sortList(ListNode head) {
List<Integer> numList = new ArrayList<>();
while (head != null) {
numList.add(head.val);
head = head.next;
}
Collections.sort(numList);
ListNode dummy = new ListNode(), prev = dummy;
for (int num : numList) {
prev.next = new ListNode(num);
prev = prev.next;
}
return dummy.next;
}
}
评论区