[[[ C++ ]]] Top 80% O(N) With O(1) Memory - Slick Rick Solution [[KoDerZ KamP]]
\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        \n        //We will store the solution after sentinel..\n        ListNod
```\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        \n        //We will store the solution after sentinel..\n        ListNode *aSentinel = new ListNode(0);\n        ListNode *aPrev = NULL;\n        \n        //We pluck nodes out from the original list, one at a time.\n        ListNode *aInsert = head;\n        ListNode *aNextInsert = NULL;\n        \n        //We search through the sorted partial result.\n        ListNode *aSearch = NULL;\n        \n        while (aInsert) {\n            \n            //a begin\n            aNextInsert = aInsert->next;\n            \n            //Find the spot to insert the node...\n            \n            aPrev = aSentinel;\n            aSearch = aSentinel->next;\n            while (aSearch != NULL && aSearch->val < aInsert->val) {\n                aPrev = aSearch;\n                aSearch = aSearch->next;\n            }\n            \n            aPrev->next = aInsert;\n            aInsert->next = aSearch;\n            \n            //a end\n            aInsert = aNextInsert;\n        }\n        \n        ListNode *aResult = aSentinel->next;\n        delete aSentinel;\n        return aResult;\n    }\n};\n```\n\nWe keep the code short by using a sentinel node.
[]