Simple Solution with step by step explaination
In this question, we have to perform insertion sorting on a linked list.\nTherefore, to first understand this, we first need to know about Insertion sort.\nIn I
In this question, we have to perform insertion sorting on a linked list.\nTherefore, to first understand this, we first need to know about Insertion sort.\nIn Insertion Sort, the array (linked list in this case) is divided into two parts, the unsorted and sorted parts.\n\nElements from unsorted part are picked and placed at their correct sorted position.\n\nIn this, we will be using three pointers *prev*, *curr* and *tmp* for storing previous values, current values and for storing head of the linked list.\n\nAt first, we have to check for edge cases, that is, whether the list is empty or has only one element. In both of these cases, we have to just simply return the head as no computation is required.\n\nAfter checking for the above mentioned cases, we have to perform sorting.\nFor every element, we have to check whether the element is at its correct position or not.\n\nIf the current value is less than the previous value, then we have to swap them, and furthermore, we have to now check the previously sorted part of the list as well including the currently sorted element.\n\nFor example consider the list:\n**[1,2,4,5,3]**\nIn this, [1,2,4,5] is sorted part but [3] is not.\nhere, **prev points to 5 and curr points to 3**\nsince, 3 is less than 5, we will swap these.\nAfter swapping:\n**[1,2,4,3,5]**\nNow, we can see that 3 is not at its correct position, so we have to check in the Sorted part as well i.e. **[1,2,4]**\nHere, we will use **tmp** pointer to iterate linked list from the head till that element, and compare that element (here, 3) with all the elements, and position it accordingly.\n\nOnce, we complete the comparing and swapping for all the remaining elements, our resultant list is sorted, which we return.\n\nHere\'s the complete **code** for your reference:\n```\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* prev = nullptr, *curr=head, *tmp=head;\n        if(head==nullptr || head->next==nullptr)\n            return head;\n        else{\n            prev = head;\n            curr = head->next;\n            while(curr!=nullptr){\n                if(prev->val > curr->val){\n                    swap(prev->val, curr->val);\n                    tmp = head;\n                    while(tmp!=prev){\n                        if(tmp->val > prev->val){\n                            swap(tmp->val, prev->val);\n                        }\n                        tmp = tmp->next;\n                    }\n                }\n                prev=prev->next;\n                curr=curr->next;\n            }\n            return head;\n        }\n    }\n};\n```\n\n***PS: Do give it an upvote if this helped.\nIn case of any queries or suggestions feel free to comment below.\nThanks!***
['C']