# 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:
        if not head or not head.next:
            return head
        temphead=ListNode(None)
        temphead.next=head
        goer=head.next
        head.next=None
        while goer:
            check=temphead
            while check.next and goer.val>check.next.val:
                check=check.next
            temp1=check.next
            temp2=goer.next
            check.next=goer
            goer.next=temp1
            goer=temp2
        return temphead.next

'''
执行用时：
1664 ms
, 在所有 Python3 提交中击败了
17.25%
的用户
内存消耗：
15.2 MB
, 在所有 Python3 提交中击败了
83.95%
的用户

'''