```
class Solution:
# @param head, a ListNode
# @return a ListNode
def insertionSortList(self, head):
if None == head:
return None
#记录尾部节点
tail_node = head
next_node = head.next
while None != next_node:
if head.val >= next_node.val:
## 更新头指针和next_node
tmp = next_node.next
next_node.next = head
head = next_node
next_node = tmp
elif tail_node.val <= next_node.val:
#小于或等于尾部节点
tail_node.next = next_node
tail_node = next_node
next_node = next_node.next
else:
#从头部查找合适位置进行插入操作
tmp = head.next
prev = head
while None != tmp:
if tmp.val > next_node.val:
break;
prev = tmp
tmp = tmp.next
prev.next = next_node
next_node = next_node.next
prev.next.next = tmp
tail_node.next = None
return head
```