Python solution
Time complexity: O(n^2), space complexity: O(1).\n\n\nclass Solution:\n    def insertionSortList(self, head):\n        """\n        :type head: ListNode\n      
Time complexity: `O(n^2)`, space complexity: `O(1)`.\n\n```\nclass Solution:\n    def insertionSortList(self, head):\n        """\n        :type head: ListNode\n        :rtype: ListNode\n        """\n        if not head or not head.next:\n            return head\n        dummy = ListNode(float(\'inf\'))\n        dummy.next = head\n        pre1 = head\n        ptr1 = head.next\n        while ptr1: # keep the loop invariant that nodes between dummy and ptr1 are sorted\n            pre2 = dummy\n            ptr2 = dummy.next\n            while ptr2 != ptr1 and ptr2.val <= ptr1.val: # ptr2 searches for the right place to insert ptr1\n                pre2 = ptr2\n                ptr2 = ptr2.next\n            if ptr2 == ptr1:\n                pre1 = ptr1\n                ptr1 = ptr1.next\n            else:\n                pre2.next = ptr1\n                tmp = ptr1.next\n                ptr1.next = ptr2\n                ptr2 = ptr1\n                ptr1 = tmp\n                pre1.next = ptr1\n        return dummy.next\n```
[]