[c++] solution O(1) space
The idea is to create a dummy node that would be the head of the sorted part of the list. Iterate over the given list and one by one add nodes to the sorted lis
##### The idea is to create a dummy node that would be the head of the sorted part of the list. Iterate over the given list and one by one add nodes to the sorted list in the appropriate place following the insertion sort algorithm.\n\n\t/**\n\t * Definition for singly-linked list.\n\t * struct ListNode {\n\t *     int val;\n\t *     ListNode *next;\n\t *     ListNode() : val(0), next(nullptr) {}\n\t *     ListNode(int x) : val(x), next(nullptr) {}\n\t *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n\t * };\n\t */\n\tclass Solution {\n\tpublic:\n\t\tListNode* insertionSortList(ListNode* head) {\n\t\t\tif(head == nullptr) return head;\n\n\t\t\tListNode *a = new ListNode(0);\n\t\t\tListNode *cur = head;\n\t\t\tListNode *pre = a;\n\t\t\tListNode *next = nullptr;\n\n\t\t\twhile(cur != nullptr){\n\t\t\t\tnext = cur->next;\n\t\t\t\twhile(pre->next != nullptr && pre->next->val < cur -> val){\n\t\t\t\t\tpre = pre -> next;\n\t\t\t\t}\n\n\t\t\t\tcur->next = pre->next;\n\t\t\t\tpre->next = cur;\n\t\t\t\tpre = a;\n\t\t\t\tcur = next;\n\t\t\t}\n\t\t\treturn a->next;\n\t\t}\n\t};\n\t\n**Complexity**\n* Time: O(n ^ 2) \n* Space: O(1)
['C']