本节通过对链表进行插入排序,对之前所学的直接插入排序法进行灵活应用.采用直接插入排序法实现按照元素从小到大的顺序对链表进行排序.

解读要求,要将待排序的集合分为两部分,一部分是已排序的子集合,另一部分是待排序的集合.然后在待排序的集合中取出一个元素插入有序子集合中的合适位置,使子集合有序.

链表的定义结构如下:

class ListNode:def __init__(self,x):self.val = xself.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.nextcurrent = head

 接下来就是寻找插入位置的阶段,分为两种情况.一种是当p要插入位置在head头指针之前,不但要让p的下一个节点指向head,还要修改p为头指针.代码如下:

if(p.val<=head.val):p.next = headhead = p

最后,更新p节点为起初保存的p_head节点,继续进行循环即可