Python中链表的插入排序（Insertion Sort）实现
链表的插入排序是通过将未排序的元素插入到已排序的位置来排序链表的一种方法。算法的基本思想是，将未排序的元素依次插入到已排序的链表中，直到所有元素都被处理。
实现链表的插入排序可以按照以下步骤进行：
- 定义一个新的链表，代表已排序的链表。
- 遍历原链表中的每个节点，将其从原链表中删除。
- 将该节点插入到新链表中，使得新链表中的节点按照从小到大的顺序排列。
- 最后返回新链表，其中的节点已经按照从小到大的顺序排列。
下面是Python中链表的插入排序代码实现：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def insertionSortList(head: ListNode) -> ListNode: # 定义一个新的链表，代表已排序的链表 dummy = ListNode() # 遍历原链表中的每个节点，将其从原链表中删除 while head: # 取出当前节点 curr = head head = head.next # 将该节点插入到新链表中 prev = dummy while prev.next and prev.next.val < curr.val: prev = prev.next curr.next = prev.next prev.next = curr # 返回新链表，其中的节点已经按照从小到大的顺序排列 return dummy.next
接下来，我们演示一下链表插入排序的使用：
# 创建一个链表 head = ListNode(4) head.next = ListNode(2) head.next.next = ListNode(3) head.next.next.next = ListNode(1) # 输出原链表 temp = head while temp: print(temp.val, end=" -> ") temp = temp.next print("None") # 链表排序 head = insertionSortList(head) # 输出排序后的链表 temp = head while temp: print(temp.val, end=" -> ") temp = temp.next print("None")
输出结果为：
4 -> 2 -> 3 -> 1 -> None 1 -> 2 -> 3 -> 4 -> None
在上述例子中，原链表为4->2->3->1，经过插入排序之后，链表变成了1->2->3->4。可以看出，链表的插入排序算法已经成功地对链表进行了排序。
相关文章