C++ | Insertion sort | Easy Solution
\n# Complexity\n- Time complexity:O(n)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity:O(n)\n Add your space complexity here, e.g. O(n) \n\n# 
\n# Complexity\n- Time complexity:`O(n)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:`O(n)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        \n        // if list contains only one node\n        if(!head->next) return head;\n\n        // dummy node for sorted list & pointer at dummy list\n        ListNode* sorted = new ListNode();\n        ListNode* ptr = sorted;   // tail\n\n        // create first node of sorted list using first node of head\n        ptr->next = new ListNode(head->val);\n        ptr = ptr->next; // update ptr(tail)\n\n        // updating head of input list\n        head = head->next;\n\n        while(head){\n            // if current node\'s value is greater than last node of sorted list\n            // need to update tail(ptr) \n            if(head->val > ptr->val){\n                ptr->next = new ListNode(head->val);\n                ptr = ptr->next;\n            }\n            else{\n                // otherwise insert node according to value\n                ListNode* pre = sorted;\n                ListNode* curr = sorted->next;\n\n                while(curr){\n                    if(curr->val >= head->val){\n                        pre->next = new ListNode(head->val);\n                        pre->next->next = curr;\n                        break;\n                    }\n                    pre = curr;\n                    curr = curr->next;\n                }\n            }\n            // move forward in input list\n            head = head->next;\n        }\n        // return sorted list\n        return sorted->next;\n    }\n};\n```
['Linked List', 'Sorting', 'C++']