☆打卡算法☆LeetCode 147. 对链表进行插入排序 算法解析
☆打卡算法☆LeetCode 147. 对链表进行插入排序 算法解析
恬静的小魔龙
发布于 2022-08-07 10:38:34
发布于 2022-08-07 10:38:34
一、题目
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)。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-06-07，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录