c++ | | 2 approches | | clear solution
1st approch\nclass Solution {\npublic:\n\n    ListNode insertionSortList(ListNode head) {\n    ListNode nxt = head -> next;\n    while(nxt != NULL)\n    {\n    
1st approch\nclass Solution {\npublic:\n\n    ListNode* insertionSortList(ListNode* head) {\n    ListNode *nxt = head -> next;\n    while(nxt != NULL)\n    {\n        ListNode *curr = head;\n        while(curr != nxt)\n        {\n            if(nxt -> val < curr -> val)\n                swap(curr , nxt );\n            \n            curr = curr -> next;\n        }\n        nxt = nxt -> next;   \n    }\n    return head;\n}\n\n};\n\n2nd approch\n\nclass Solution {\npublic:\n\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* dummy=new ListNode(-1);\n        \n        ListNode* curr=head;\n        \n        while(curr!=NULL){\n            ListNode* temp=curr->next;\n            ListNode* prev=dummy;\n             ListNode* nxt=dummy->next;\n            \n            while(nxt!=NULL){\n                if(nxt->val>curr->val) break;\n                \n                prev=nxt;\n                nxt=nxt->next;\n            }\n            curr->next=nxt;\n            prev->next=curr;\n            curr=temp;\n        }\n        return dummy->next;\n        \n        \n    }\n};\n\ntime complexity for this will be - o(n).
['Linked List', 'C']