C++ Simple and Short Explained Solution, No Extra Space
Idea:\nWe start the new sorted list with a zero node, so that it will be easier to insert in every position.\nWe iterate through the list with the head pointer.
**Idea:**\nWe start the new sorted list with a zero node, so that it will be easier to insert in every position.\nWe iterate through the list with the `head` pointer.\nFor each node, we use the function `insert` to iterate through the new sorted list and find the right insertion position.\nWe return `new_head->next` because our zero node will always be first and we don\'t want it.\n\n**Time Complexity:** O(n^2)\n**Space Complexity:** O(1)\n```\nclass Solution {\npublic:\n    void insert(ListNode* head, ListNode* node) {\n        while (head->next && head->next->val < node->val) head = head->next;\n        node->next = head->next;\n        head->next = node;\n    }\n    \n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* new_head = new ListNode(0);\n\n        while (head) {\n            ListNode* node = head;\n            head = head->next;\n            insert(new_head, node);\n        }\n        \n        return new_head->next;\n    }\n};\n```\n**Like it? please upvote!**
['C']