侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-05-11 / 0 评论 / 0 点赞 / 44 阅读 / 228 字 / 正在检测是否收录...

题目

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;
    }
}
0

评论区