对链表进行插入排序(Python)
- 作者: Black66506319
- 来源: 51数据库
- 2021-09-20
1、题目描述
https://leetcode-cn.com/problems/insertion-sort-list/
对链表进行插入排序。
插入排序算法:
- 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
- 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
- 重复直到所有输入数据插入完为止。
输入: -1->5->3->4->0
输出: -1->0->3->4->5
2、代码详解
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
dummy = ListNode(0)
dummy.next = head
last_sorted = head # 已排序部分的最后一个节点
cur = head.next # 待插入的
while cur:
if last_sorted.val <= cur.val:
last_sorted = last_sorted.next
else:
# 从链表的头节点开始往后遍历链表中的节点,寻找插入 cur 的位置
prev = dummy
while prev.next.val <= cur.val:
prev = prev.next
# 插入操作:令 prev 为插入 cur 的位置的前一个节点
last_sorted.next = cur.next
cur.next = prev.next
prev.next = cur
cur = last_sorted.next
return dummy.next
时间复杂度:O(n*n)
https://leetcode-cn.com/problems/insertion-sort-list/solution/dui-lian-biao-jin-xing-cha-ru-pai-xu-by-leetcode-s/
推荐阅读