算法-堆/归并排序-排序链表

这篇具有很好参考价值的文章主要介绍了算法-堆/归并排序-排序链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

算法-堆/归并排序-排序链表

1 题目概述

1.1 题目出处

https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-interview-150

1.2 题目描述

算法-堆/归并排序-排序链表,算法,链表,数据结构
算法-堆/归并排序-排序链表,算法,链表,数据结构

2 优先级队列构建大顶堆

2.1 思路

  1. 优先级队列构建小顶堆
  2. 链表所有元素放入小顶堆
  3. 依次取出堆顶元素,链表串起来即可

2.2 代码

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((n1,n2)->n1.val-n2.val);
        ListNode newHead = new ListNode();
        while(null != head) {
            minHeap.add(head);
            head = head.next;
        }
        ListNode tmp = minHeap.poll();
        tmp.next = null;
        newHead.next = tmp;
        while(minHeap.size()>0) {
            ListNode cur = minHeap.poll();
            tmp.next = cur;
            tmp = cur;
            tmp.next = null;
        }
        return newHead.next;
    }
}

2.3 时间复杂度

O(nlogn)
算法-堆/归并排序-排序链表,算法,链表,数据结构

2.4 空间复杂度

O(n)

3 归并排序

3.1 思路

  1. 用快慢指针法,找到链表中间位置
  2. 将链表拆分成两条子链表
  3. 对子链表分别排序
  4. 将排序后的子链表合并排序

3.2 代码

class Solution {
    public ListNode sortList(ListNode head) {
        if (null == head) {
            return null;
        }
        if (null == head.next) {
            return head;
        }

        ListNode fast = head.next;
        ListNode slow = head;

        // 找到fast到中间位置
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 切断两个链表
        fast = slow.next;
        slow.next = null;

        // 分别对两个子链表排序
        slow = sortList(head);
        fast = sortList(fast);

        ListNode dummy = new ListNode();
        head = dummy;

        // 合并已排序的两个子链表
        while (null != slow && null != fast) {
            if (slow.val <= fast.val) {
                head.next = slow;
                slow = slow.next;
            } else {
                head.next = fast;
                fast = fast.next;
            }
            head = head.next;
        }
        while (null != slow) {
            head.next = slow;
            slow = slow.next;
            head = head.next;
        }
        while (null != fast) {
            head.next = fast;
            fast = fast.next;
            head = head.next;
        }
        return dummy.next;
    }
}

3.3 时间复杂度

算法-堆/归并排序-排序链表,算法,链表,数据结构
O(nlogn)

3.4 空间复杂度

O(logn)调用栈深度

4 非递归方式(循环)

4.1 思路

3中使用递归方式,空间复杂度O(logn),可改为循环方式达到O(1)的空间复杂度文章来源地址https://www.toymoban.com/news/detail-723304.html

4.2 代码


4.3 时间复杂度

4.4 空间复杂度

参考文档

  • Sort List (归并排序链表)

到了这里,关于算法-堆/归并排序-排序链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包