C++ Easy Solution in O(1) space.
\nListNode* insertionSortList(ListNode* head) {\n        // if list is empty or has only one node\n        if(head == NULL || head->next == NULL)\n            r
```\nListNode* insertionSortList(ListNode* head) {\n        // if list is empty or has only one node\n        if(head == NULL || head->next == NULL)\n            return head;\n\t\t\t\n        // make an empty list, it will store nodes in sorted order\n        ListNode* newList = NULL;\n    \n        ListNode* current = head;\n        \n        while(current!=NULL){\n            \n            // store current\'s next in a variable\n            ListNode* nextt = current->next;\n            \n            // insert this node is its correct position in the new list.\n            if(newList == NULL || newList->val >= current->val){\n                ListNode* temp = newList;\n                newList = current;\n                newList->next = temp;\n            }\n            else\n            {\n                ListNode* temp = newList;\n                while(temp && temp->next && temp->next->val <= current->val)\n                {\n                    temp = temp->next;\n                }\n                ListNode* t = temp->next;\n                temp->next = current;\n                temp->next->next=t;\n            }\n            // go the the next node\n            current = nextt;\n        }\n        return newList;\n    }\n```
[]