2 Implementation | Explained
Idea?\n We need to sort the list using Insertion Sort.\n Insertion Sort works in O(n^2) time, each time picking up the new element and inserting back this eleme
**Idea?**\n* We need to sort the list using Insertion Sort.\n* Insertion Sort works in **O(n^2) time**, each time picking up the new element and **inserting back this element** at the correct position in the sorted list found till now.\n\n**Implementation 1:-(Not Efficient)**\n* Each time when we pick up the new element, we need to **traverse in a backward manner** in the sorted list to insert this element at the correct position right?\n* How do we traverse in a backward manner?\n* We will be **reversing the sorted list up to the current node**.\n* Then, we\'ll insert this new value at the correct position.\n* Again **restore the original list by reversing again**.\n\n```\nclass Solution {\npublic:\n    // Time Complexity:- O(n^2)\n    // Space Complexity:- O(1)\n    // reverse the List upto the given node\n    void reverseList(ListNode* head,ListNode* upto){\n        ListNode *prev = NULL;\n        while(head!=upto){\n            ListNode* temp = head->next;\n            head->next = prev;\n            prev = head;\n            head = temp;\n        }\n    }\n    // insert the value at correct position\n    void InsertValue(ListNode* curr){\n        ListNode *nxt = curr->next;\n        while(nxt!=nullptr and nxt->val>curr->val){\n            swap(nxt->val,curr->val);\n            nxt = nxt->next;\n            curr = curr->next;\n        }\n    }\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* curr = head;\n        while(curr!=nullptr){\n            ListNode* temp = curr->next;\n            reverseList(head,curr->next); // reverse the list prior to this node\n            InsertValue(curr); // insert the value\n            reverseList(curr,nullptr); // reverse the previous list again\n            curr->next = temp;\n            curr = curr->next;\n        }\n        return head;\n    }\n};\n```\n\n**Implementation 2:-(Efficient)**\n* The above implementation is quite a hectic task, Can we improve it? **Can we insert a dummy node**?\n* Okay, Let\'s make a dummy node.\n* Each time when we encounter a new element, we\'ll find the correct position from the start of the sorted list(*starting from dummy node*) and find the position where this new value should be inserted.\n* **Note:- Here we aren\'t reversing any list here.**\n\n```\nclass Solution {\npublic:\n    // Time Complexity:- O(n^2)\n    // Space Complexity:- O(1)\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* dummy = new ListNode(-5005);\n        ListNode* curr = head;\n        while(curr!=nullptr){\n            ListNode* nxt = curr->next; // store next node for iteration\n            ListNode* iter = dummy;\n            // iterate from the beginning and find the suitable position of curr->val\n            while(iter->next!=nullptr and iter->next->val<curr->val)\n                iter = iter->next;\n            curr->next = iter->next;\n            iter->next = curr; // insert node at this position\n            curr = nxt;\n        }\n        return dummy->next;\n    }\n};\n```\n**Don\'t Forget to Upvote!**\n
[]