[C++] Pointer-based Solution Explained, 100% Time, 90% Space
Ah, gotta love starting the day with classic algorithms you otherwise would just see again on textbooks and manuals :)\n\nIn order to proceed with this one, we 
Ah, gotta love starting the day with classic algorithms you otherwise would just see again on textbooks and manuals :)\n\nIn order to proceed with this one, we need to first of all check if we are dealing with an empty list: if so, we just return `NULL`.\n\nOtherwise, we create 3 support variables, all `ListNode` pointers:\n* `tail`, initialised to be `head` will delimit up to where our sorted domain extends;\n* `curr` is the node we are currently considering and putting in sorted order;\n* `iter`, finally, it is a support variable for when we need to go and splice `curr` if it is not the newest minimum or the newest maximum; I know I might have not used it, just splicing `curr` so that it would bubble up to his position, but that seemed needlessly expensive and not worth saving the tiny amount of memory an extra pointer would cost us - so, unless your interviewer really wants you to consider other approaches (like dealing with devices of very little memory, but then not sure how they would handle linked lists), just discuss it quickly and make your own call of what is best.\n\nThen we have our main loop and we will proceed until we have something else to parse, that is to say as long as `tail->next`. Notice we do not need to check if `tail` exist, since we initialised it to `head` and we checked before that `head` has to be non `NULL`.\n\nInside our loops we will:\n* check if `curr` is the newest maximum and thus replace `tail` with it;\n* get the next value after `tail` out and assign it to `curr`;\n* check if `curr` is the newest minimum and thus replace `head` with it;\n* check for all the other cases, assigning `head` to `iter` initially and gradually increasing it, checking if `curr` fits between `iter` and `iter->next`.\n\nOnce we are done parsing the whole list, we return `head` :)\n\nThe code:\n\n```cpp\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        if (!head) return NULL;\n        ListNode *tail = head, *curr, *iter;\n        while (tail->next) {\n            // checking if the next one is already the next bigger\n            if (tail->val <= tail->next->val) {\n                tail = tail->next;\n                continue;\n            }\n            // taking a new node to parse, curr, out of the list\n            curr = tail->next;\n            tail->next = curr->next;\n            // checking if curr will become the new head\n            if (curr->val < head->val) {\n                curr->next = head;\n                head = curr;\n                continue;\n            }\n            // all the other cases\n            iter = head;\n            while (iter != tail) {\n                // checking when we can splice curr between iter and the following value\n                if (curr->val < iter->next->val) {\n                    curr->next = iter->next;\n                    iter->next = curr;\n                    break;\n                }\n                // moving to the next!\n                iter = iter->next;\n            }\n        }\n        return head;\n    }\n};\n```
['Graph', 'C', 'C++']