【算法面试必刷Java版十二】单链表的排序

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：单链表的排序

描述：

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：0<n≤100000

要求：时间复杂度 O(nlogn)

思路：插入排序

1. 新建链表
2. 遍历原链表
3. 将每一个值插入到新链表中

额外：明确一个概念

数组和链表是常见的两种存储数据的结构：

数组的优势、缺点：

构建简单、能够根据下标在O(1)时间内查询到某个元素。数组是连续的空间，增加和删除某一元素时，需要移动大部分数组元素，时间复杂度是O(n)。

链表的优势、缺点：

灵活分配空间、能在O(1)的时间内删除或添加元素。缺点是获取元素比较耗时。

代码：

/**
 * 链表的优势：插入和删除
 */
public ListNode sortInList(ListNode head) {
    // write code here
    ListNode pre = new ListNode(Integer.MIN_VALUE);
    ListNode cur;
    while (head != null) {
        cur = pre;
        ListNode node = head;
        head = head.next;
        while (cur != null) {
            if (cur.val < node.val && (cur.next == null || cur.next.val >= node.val)) {
                node.next = cur.next;
                cur.next = node;
                break;
            }
            cur = cur.next;
        }
    }
    return pre.next;
}

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101