对链表进行插入排序
本节通过对链表进行插入排序,对之前所学的直接插入排序法进行灵活应用.采用直接插入排序法实现按照元素从小到大的顺序对链表进行排序.
解读要求,要将待排序的集合分为两部分,一部分是已排序的子集合,另一部分是待排序的集合.然后在待排序的集合中取出一个元素插入有序子集合中的合适位置,使子集合有序.
链表的定义结构如下:
class ListNode:
def __init__(self,x):
self.val = x
self.next = None
要将链表分为两个部分,需要两个变量分别保存两个部分的头指针.
head变量:表示有序子链表的头指针
p变量:表示待排序链表的头指针,即head所指向的下一个位置,其代码如下:
p = head.next
head.next = None然后对以p为头指针的未排序链表进行遍历,找到p节点应该插入的位置.
p_head变量:表示用于储存p的下一个位置节点的变量,以免p节点完成插入之后无法找到下一个待排序节点.因此在循环中,在对每一个节点找寻插入位置时应先将下一个待排序节点保存起来.
current变量:表示头节点,在寻找合适插入位置时向后遍历.
代码如下:
while(p is not None):
p_head = p.next
current = head接下来就是寻找插入位置的阶段,分为两种情况.一种是当p要插入位置在head头指针之前,不但要让p的下一个节点指向head,还要修改p为头指针.代码如下:
if(p.val<=head.val):
p.next = head
head = p最后,更新p节点为起初保存的p_head节点,继续进行循环即可