C/C++ Compatible Indirect Pointer solution with O(1) space | 0ms (100%)
<--------------\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F PLEASE UPVOTE \u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F----------
<--------------\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F PLEASE UPVOTE \u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F\u2B06\uFE0F--------------->\n\nUsing an indirect pointer to the run (where we tried to maintain the sorted partition up to) and perform sorted insert between `head` and `*run`.\n\nDetailed Explanation at each step:\n```\n// Case 1: we still have a sorted list up to `*run`: if (*run)->val >= max\n| <= x |  x  |      ...      |\n|<- sorted ->|<- unsorted  ->|\n          ^max == *run\n// so, we can just advance the run to it\'s pointee\'s `next`\n------------------------------------------------------------\n// Case 2: we have to move`*run` in front to maintain the non-descreasing sequence: if (*run)->val < max\n| < x | >= x |  x  |  ...   |\n|<- sorted ->|<- unsorted ->|\n ^head ... ^max ^(*run)\n\n// Now, just perform a sorted insert of `*run`, between `head` and `max`\n// we can declare an indirect pointer `indirect` initialized to address of `head`, and\n// iterate until it points to a node such that node->val >= x (i.e. (*run)->val)\n| < x | >= x |  x  |  ...   |\n|<- sorted ->|<- unsorted ->|\n       ^(*indirect) (the first node of the >= x partition)\n\n// finally we can remove the pointee of `run` (i.e. `*run`) and insert at `*indirect`, such that\n| < x | x |  >= x  |      ...      |\n|<-     sorted   ->|<- unsorted  ->|\n               ^max ^(*run)\n// NOTE: run is the address of the `next` of the node having `val` == max\n// NOTE: we don\'t need to advance the run pointer in this case\n```\n\n\nCode:\n```C++\nclass Solution {\npublic:\n    void insert_before(ListNode **at, ListNode *node) {\n        node->next = *at;\n        *at = node;\n    }\n    \n    ListNode *remove(ListNode **at) {\n        ListNode *result = *at;\n        *at = result->next;\n        result->next = NULL;\n        return result;\n    }\n    \n    ListNode *insertionSortList(ListNode *head) {\n        ListNode **run = &head;\n        \n        int max = INT_MIN;\n        \n        // until the last node\n        while (*run) {\n            max = std::max(max, (*run)->val);\n \xA0 \xA0 \xA0 \xA0 \xA0 \xA0if ((*run)->val < max) {\n \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0  // case 2: sorted insert\n \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0ListNode **indirect = &head;\n \xA0 \xA0 \xA0 \xA0 \xA0 \xA0 \xA0  // walk to the next node until we hit the first node of the larger partition\n                while ((*indirect)->val < (*run)->val)\n                    indirect = &(*indirect)->next;\n                \n                insert_before(indirect, remove(run));\n            } else {\n                // case 1\n                run = &(*run)->next;\n            }\n        }\n        return head;\n    }\n};\n```
['C++']