Simple Solution || O(N^2) time || O(1) space
\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(nullpt
\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    ListNode* insertionSortList(ListNode* head) {\n        // idea is we maintain a prev list & for each node we check in prev list until all elements are smaller then insert the node between the smaller & greater elements.\n        if(!head || !head->next)return head;\n        ListNode* dummy=new ListNode(INT_MIN);\n        ListNode* tail=dummy;\n        ListNode* curr=head;\n        while(curr){\n            ListNode * next=curr->next;\n            while(tail->next && tail->next->val<curr->val){\n                tail=tail->next;\n            }\n            curr->next=tail->next;\n            tail->next=curr;\n            tail=dummy;\n            curr=next;\n        }\n        return dummy->next;\n        \n    }\n};\n```
['Sorting', 'C++']