☆打卡算法☆LeetCode 148. 排序链表 算法解析

恬静的小魔龙 发表于 2022/06/29 11:28:20 2022/06/29
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定链表的头结点,返回按照升序排序的链表。”题目链接:来源:力扣(LeetCode)链接: 148. 排序链表 - 力扣(Lee...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定链表的头结点,返回按照升序排序的链表。”

题目链接:

来源:力扣(LeetCode)

链接: 148. 排序链表 - 力扣(LeetCode)

2、题目描述

给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。

image.png

示例 1:
输入: head = [4,2,1,3]
输出: [1,2,3,4]
示例 2:
输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

二、解题

1、思路分析

147题是实现链表的插入排序,时间复杂度是O(n2)。

这道题要求时间复杂度更低的排序算法,要求达到O(n log n)的时间复杂度。

可以实现O(n log n)的时间复杂度的排序算法有归并排序、堆排序和快速排序,其中最适合链表的排序算法是归并排序。

首先来了解一下什么是归并排序,归并排序是自顶向下直接合并的方式进行排序,具体过程如下:

  • 1、找到链表中点,以中点为界,将链表拆成两个子链表。
  • 2、对两个子链表分别排序。
  • 3、将两个排序后子链表合并,得到完成链表。

因为上述的过程是通过递归实现的,所以时间复杂度为O(n log n),空间复杂度为O(log n)。

2、代码实现

代码参考:

class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }
}

image.png

3、时间复杂度

时间复杂度:O(n log n)

其中n是链表的长度。

空间复杂度:O(log n)

其中n是链表的长度,空间复杂度主要取决于递归调用的栈空间。

三、总结

通过递归实现链表的归并排序,主要分成两步。

第一步是分割成两个子链表。

可以使用快慢指针,快指针每次移动2步,慢指针每次移动1步,当快指针移动到链表末尾时,慢指针指向链表的节点就是链表的中点。

第二步是子链表递归分别排序。

设置两个指针分别指向两个链表头部,比较两个指针处节点值大小,由小到大加入合并到链表头部,指针交替前进,直到添加完两个链表。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。