# Definition for singly-linked list.

 # class ListNode:

 #     def __init__(self, x):

 #         self.val = x

 #         self.next = None

 class Solution:

     # @param head, a ListNode

     # @return a ListNode

     def insertionSortList(self, head):

         if head is None or head.next is None:

             return head

         dummyhead = ListNode(0)

         dummyhead.next = head

         curr = dummyhead.next

         while curr.next is not None:

             if curr.next.val < curr.val:

                 pre = dummyhead

                 while pre.next.val < curr.next.val:

                     pre = pre.next

                 tmp = curr.next

                 curr.next = tmp.next

                 tmp.next = pre.next

                 pre.next = tmp

             else:

                 curr = curr.next

         return dummyhead.next