Clear cpp solution using insertion sort | beats 99.3% | O(1) space
Approach\n Describe your approach to solving the problem. \n\n##### We will follow the procedure of insertion sort as we do for array.\nFor the solution I have 
# Approach\n<!-- Describe your approach to solving the problem. -->\n\n##### We will follow the procedure of insertion sort as we do for array.\nFor the solution I have defined some helper functions namely-\n\n1. `insertNode` which is vanilla insertion in a linked list where the pointer of node after which toinsert is known. Note that it assumes that the next attribute of toinsert node is nullptr.\n2. `insertInSorted` which inserts the toinsert node to a linked list which is given as sorted and its head pointer is given. I have used linear search to first locate the suitable position and then have used the `insertNode` function to insert the toinsert node. After insertion it returns the head of the new linkedlist obtained.Note that here also the next pointer of toinsert node must be nullptr initially.\n\nIn the actual `insertionSortList` function we know that linked list with only one node will be sorted in itself so we start from head->next.\n- We will initialize two pointers `curr` and `prev`. \n`prev` will keep track of last node of the sorted linkedlist that we will constructively build starting from the head node.\n`curr` will the current node that we want to add to the sorted list that we are building in each iteration.\n- In each iteration untill `curr != nullptr`, we first check that if `curr->val>=prev->val` which is to say that curr is already larger than the sorted list, we do nothing and advance both pointers by one node.\nelse we crucially first isolate the node curr by connecting prev to `curr->next` and the setting `curr->next = null` then we use the `insertInSorted` function to insert the curr node to the sorted array build.\n- Finally we return the head.\n\n\n# Complexity\n- Time complexity: $$O(n^2)$$ $$n : number-of-nodes$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\nclass Solution {\npublic:\n    void insertNode(ListNode* node, ListNode* toinsert){\n        if(node->next == nullptr){\n            node->next = toinsert;\n            return;\n        }\n        toinsert->next = node->next;\n        node->next = toinsert;\n        return;\n    }\n    ListNode* insertInSorted(ListNode* head, ListNode* toinsert){\n        if(toinsert->val <= head->val){\n            toinsert->next = head;\n            head = toinsert;\n            return head;\n        }\n        ListNode* curr = head;\n        bool flag = false;\n        while(curr->next != nullptr){\n            if(curr->val <= toinsert->val && curr->next->val >= toinsert->val){\n                insertNode(curr, toinsert);\n                flag = true;\n                break;\n            }\n            curr = curr->next;\n        }\n        if(!flag) insertNode(curr, toinsert);\n        return head;\n    }\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* prev = head;\n        ListNode* curr = head->next;\n        while(curr != nullptr){\n            if(prev->val <= curr->val){\n                prev = curr;\n                curr = curr->next;\n            }\n            else{\n                prev->next = curr->next;\n                curr->next = nullptr;\n                head = insertInSorted(head, curr);\n                curr = prev->next;\n            }\n        }\n        return head;\n    }\n\n};\n```
['Linked List', 'C++']