Short, simple and fast c++ solution. No need for a dummy or similar to handle the new head creation.
A lot of solutions allocate a dummy node with the intensions of using the dummy.next to point to the head of the new list. It\'s much simpler to instead use a p
A lot of solutions allocate a dummy node with the intensions of using the dummy.next to point to the head of the new list. It\'s much simpler to instead use a pointer to a pointer that stores the address of either the pointer to the new head or the next pointer of the previous node. That way an update to whichever pointer is being pointed to (head or next), will either update the head directly or update the next of the previous node.\n\nIt\'s one of those things that\'s hard to explain with words. Saying a pointer pointing to a pointer, pointing to the head is just plain confusing. Walking through the code is the best way to understand.\n\n```\n    ListNode* insertionSortList(ListNode* head) {\n      ListNode* ret_head = nullptr;\n      while (head) {\n        ListNode* curr = head;\n        head = head->next;\n        \n        // Use a pointer to pointer so that updating either ret_head or next of the previous node is\n        // seemless and automatic.\n        ListNode** prev_next = &ret_head;\n        while (*prev_next && (*prev_next)->val < curr->val) {\n          // Update prev_next to hold the address of the next pointer for the next node.\n          prev_next = &(*prev_next)->next;\n        }\n        curr->next = *prev_next;\n        *prev_next = curr;\n      }\n      return ret_head;\n    }\n```\t\t
['C', 'C++']