☆打卡算法☆LeetCode 147. 对链表进行插入排序 算法解析

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

推荐阅读

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

一、题目

1、算法题目

“给定一个链表的头,使用插入排序对链表进行排序,返回排序后链表的头。”

题目链接:

来源:力扣(LeetCode)

链接: 147. 对链表进行插入排序 - 力扣(LeetCode)

2、题目描述

给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。

插入排序 算法的步骤:

  • 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
  • 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
  • 重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时,从输入数据中删除一个元素(红色),并就地插入已排序的列表中。

对链表进行插入排序。

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

二、解题

1、思路分析

首先来了解一下插入排序。

插入排序的主要思路就是维护一个有序序列,每次将新元素插入到已经排好序的有序表中,直到所有元素都插入到这个有序序列中。

对于数组的插入排序,数组前面部分是有序序列,遍历到有序序列后的元素的待插入位置,然后将待插入位置后面的元素都往后移动一位,然后将插入元素置于插入该位置。

对于链表来说,就是遍历链表找到要插入的位置,更新相邻接点的指针即可。

2、代码实现

代码参考:

class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) {
            return head;
        }
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode lastSorted = head, curr = head.next;
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummyHead;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        return dummyHead.next;
    }
}

image.png

3、时间复杂度

时间复杂度:O(n2)

其中n是链表的长度。

空间复杂度:O(1)

只需要常量级的变量空间。

三、总结

对于链表来说,插入元素时只需要更新相邻节点的指针即可,不用像数组插入元素要移动元素的位置。

所以链表的插入操作的时间复杂度是O(1)。

但是找到插入位置需要遍历链表,时间复杂度是O(n),因此总的时间复杂度仍然是O(n2)。

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

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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