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

推荐阅读

• CSDN主页
• GitHub开源地址
• Unity3D插件分享
• 简书地址
• 我的个人博客
• QQ群：1040082875

大家好，我是小魔龙，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;
    }
}

3、时间复杂度

时间复杂度：O(n²)

其中n是链表的长度。

空间复杂度：O(1)

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

三、总结

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

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

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