思路
维护一个排好序的链表，剩下的值如果比已排好的大，直接放到尾部，如果比之前小，则从链表头遍历，找到对应的位置并插入。
为了很好找到链表头，需要设置一个哑节点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
# 1. 如果链表为空，直接return None
if head is None:
return None
# 2. 创建一个哑节点, 指向head
pre = ListNode(0)
pre.next = head
# 3. sorted_data为已经排好序的数据，current为当前要排序的元素
sorted_data = head
current = head.next
# 4. 循环的结束条件是current走到None也就是走到最后一个元素
while current is not None:
# 当最后一个排好序的元素的值比待排序的值小，则sorted_data后移一位
if sorted_data.val <= current.val:
sorted_data = sorted_data.next
else:
# prev为头节点，为了不影响哑节点
prev = pre
# 找到排好序的第一个大于当前值的节点
while prev.next.val <= current.val:
prev = prev.next
# 这里要注意，prev目前指向的是第一个大于当前值的节点
# 这里sorted_data.next = current.next
# 是因为当前值总是在sorted_data的下一位
# 这里相当于是把当前节点撤下，挪到前面去
sorted_data.next = current.next
current.next = prev.next
prev.next = current
# 当前节点继续走，往后挪一位
current = sorted_data.next
# 返回哑节点的下一位即可
return pre.next
