leetcode147

 1 class Solution:
 2     def constructLink(self,lists):
 3         n = len(lists)
 4         if n == 0:
 5             return None
 6         if n == 1:
 7             return ListNode(lists[0])
 8         
 9         head = ListNode(lists[-1])
10         for i in range(n-2,-1,-1):
11             cur = ListNode(lists[i])
12             cur.next = head 
13             head = cur
14         return head
15     
16     def insertionSortList(self, head: ListNode) -> ListNode:
17         lists = []
18         while head != None:
19             if len(lists) == 0:
20                 lists.append(head.val)
21             else:
22                 tag = True
23                 for i in range(len(lists)):
24                     if lists[i] > head.val:
25                         lists.insert(i,head.val)
26                         tag = False
27                         break
28                 if tag:
29                     lists.append(head.val)
30             head = head.next
31         return self.constructLink(lists)