【哈希表, 排序, 暴力】排序链表

题目

148. 排序链表

---

给你链表的头结点 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;
    }
}