2.5 链表插入排序
大约 2 分钟
2.5 链表插入排序
---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
的下一个节点。
2. 链表插入排序实现代码
class Solution:
def insertionSort(self, head: ListNode):
if not head or not head.next:
return head
dummy_head = ListNode(-1)
dummy_head.next = head
sorted_list = head
cur = head.next
while cur:
if sorted_list.val <= cur.val:
# 将 cur 插入到 sorted_list 之后
sorted_list = sorted_list.next
else:
prev = dummy_head
while prev.next.val <= cur.val:
prev = prev.next
# 将 cur 到链表中间
sorted_list.next = cur.next
cur.next = prev.next
prev.next = cur
cur = sorted_list.next
return dummy_head.next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
return self.insertionSort(head)
3. 链表插入排序算法复杂度分析
- 时间复杂度:。
- 空间复杂度:。
练习题目
0148. 排序链表(链表插入排序会超时,仅做练习)