Sort a linked list using insertion sort.
利用插入排序对一个链表进行排序
思路和数组中的插入排序一样,不过每次都要从链表头部找一个合适的位置,而不是像数组一样可以从要插入的位置开始从后往前找合适的位置
class Solution(object):
def insertionSortList(self, head):
dummy = ListNode(-1)
dummy.next,cur= head,head
while cur and cur.next:
if cur.val > cur.next.val:
head = dummy
while head.next.val < cur.next.val:
head = head.next
head.next,cur.next.next,cur.next = cur.next,head.next,cur.next.next
else:
cur = cur.next
return dummy.next