C++ Solution || 16ms O(1) space
\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *   
```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode *dummy = new ListNode(-500000), *node;\n        dummy->next = head;\n        node = dummy;\n        while(head)\n        {\n            if(node->val > head->val)\n            {\n                node->next = head->next;\n                ListNode *ptr = dummy;\n                while(ptr->next->val <= head->val)\n                    ptr = ptr->next;\n                head->next = ptr->next;\n                ptr->next = head;\n                head = node->next;\n            }\n            else\n            {\n                node = node->next;\n                head = head->next;\n            }\n        }\n        \n        return dummy->next;\n        \n    }\n};\n```
[]