0147. 对链表进行插入排序 #
- 标签:链表、排序
- 难度:中等
题目大意 #
描述:给定链表的头节点 head
。
要求:对链表进行插入排序。
说明:
- 插入排序算法:
- 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
- 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
- 重复直到所有输入数据插入完为止。
- 列表中的节点数在 $[1, 5000]$ 范围内。
- $-5000 \le Node.val \le 5000$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:链表插入排序 #
-
先使用哑节点
dummy_head
构造一个指向head
的指针,使得可以从head
开始遍历。 -
维护
sorted_list
为链表的已排序部分的最后一个节点,初始时,sorted_list = head
。 -
维护
prev
为插入元素位置的前一个节点,维护cur
为待插入元素。初始时,prev = head
,cur = head.next
。 -
比较
sorted_list
和cur
的节点值。- 如果
sorted_list.val <= cur.val
,说明cur
应该插入到sorted_list
之后,则将sorted_list
后移一位。 - 如果
sorted_list.val > cur.val
,说明cur
应该插入到head
与sorted_list
之间。则使用prev
从head
开始遍历,直到找到插入cur
的位置的前一个节点位置。然后将cur
插入。
- 如果
-
令
cur = sorted_list.next
,此时cur
为下一个待插入元素。 -
重复 4、5 步骤,直到
cur
遍历结束为空。返回dummy_head
的下一个节点。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n^2)$。
- 空间复杂度:$O(1)$。