阿里在线测评题目 链表的插入排序
阿里在线测评题目 链表的插入排序
插入排序算法：
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
思路
本来的思路是两个指针，第二个指针指向的数是需要插入到正确位置的数，但是发现两个指针不够，因为两个指针无法知道插入的正确位置是哪个。所以本题需要三个指针，有一个指针一直指向链表头，当需要插入的时候再用第一个指针遍历链表，遍历到插入的正确位置时，在进行插入操作。
代码
def insertionSortList(self, head)：
'''
三个指针，pre指针保持在列表头
cur指针保持在mid后面
'''
pre = ListNode(None) # 防止有插入的列表头的情况，所以pre应该指向None
pre.next = head
if not head: return
mid = head
cur = head.next
while cur:
if cur.val > mid.val:
mid = mid.next
cur = cur.next
mid.next = cur.next
a = pre
while a.next.val < cur.val: # 找到插入位置 cur 应该插入到a后面
a = a.next
'''插入操作'''
b = a.next # 防止a.next丢失
a.next = cur
cur.next = b
cur = mid.next
return pre.next
