如何使用Python实现链表的插入排序（Insertion Sort List）
链表的插入排序是一种常见的排序算法，它的基本思想是将未排序的元素逐个插入到已排序的部分中，从而逐步形成有序序列。
下面是Python实现链表插入排序的详细步骤：
-
定义链表节点类，包括节点值和指向下一个节点的指针。
-
定义插入排序函数，函数参数为链表的头节点。
-
在插入排序函数中，定义一个新的空链表，用来存放已经排好序的节点。
-
从头节点开始遍历原链表，将每个节点插入到新链表的合适位置，使得新链表仍然保持有序。
-
返回排好序的链表的头节点。
下面是Python代码实现：
class ListNode: def __init__(self, x): self.val = x self.next = None def insertionSortList(head): """ :type head: ListNode :rtype: ListNode """ dummy = ListNode(0) #定义一个空链表 sorted_list = dummy #遍历原链表 while(head): #记录要插入的节点 cur_node = head head = head.next cur_node.next = None #从排好序的链表的头节点开始遍历 p = sorted_list.next pre = sorted_list while(p): #找到要插入的位置 if(p.val >= cur_node.val): break pre = p p=p.next #将待排序节点插入到链表中 cur_node.next = pre.next pre.next = cur_node #返回排好序的链表的头节点 return dummy.next
示例测试：
#构造一个链表 node1 = ListNode(5) node2 = ListNode(3) node3 = ListNode(1) node4 = ListNode(6) node5 = ListNode(2) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 #插入排序 new_head = insertionSortList(node1) #输出排序结果 while(new_head): print(new_head.val) new_head = new_head.next
输出结果：
1 2 3 5 6
相关文章