C++ EASY TO SOLVE || Detailed Explanation with dry run
Intuition:-\nNothing for intuition this time. Since the question is loud and clear that we need to use insertion sort[Also explained in the description of the q
**Intuition:-**\nNothing for intuition this time. Since the question is loud and clear that we need to use insertion sort[Also explained in the description of the question] for sorting the linked list .\n*A tip -Do not get intimidated by the length of code have faith in yourself that you can understand.*\n\n**Algorithm:-**\n1. Let\'s create a `newHead ` as the name suggests it will be representating our final linked list. Initialize it to NULL.\n2. Now we will traverse our original linkedlist and seperate our head nodes one at a time in each iteration to insert them in the `newHead` initiated linkedlist\n3. During insertion in `newHead` we need to take care of three conditions \n* Condition 1: If this is the first node that is being inserted in the `newHead` the node will get insertd at `newHead `\n* Condition 2:  After the the first insertion we need to check whether the next insertion will be in between or in the end of` newHead linkedlist`\n* Condition 3: To check the condition 2 we need this condition i.e we will traverse the newHead linkedlist using a temporary pointer "`root`" and find the appropriate position of the `temp` node\n4. Repeat process 2 and 3 until all the nodes are inserted to newHead\n\n[The three conditon we talked are in the form of **if** ,**elseif**, and **else** in the code given]\n\n\n**Before getting inside the code let\'s have a dry run :**\n![image](https://assets.leetcode.com/users/images/0aabafee-7553-4cb4-a1b4-a748789e3178_1639536272.2921226.jpeg)\n\n\n**Code:-**\n```\nclass Solution {\npublic:\n    ListNode* insertionSortList(ListNode* head) {\n        ListNode* newHead = NULL;//initializing the newHead for our sorted linkedlist\n        while(head){\n            // Exluding node from the original linked list we will do this one at a time\n            ListNode* temp = head;\n            head = head->next;\n            temp->next=NULL;\n            \n            //setting the first node of our final linked list \n            if(newHead == NULL) newHead = temp;\n             // if the position of element is at index 0 i.e. at the start (the temp node is the smallest of all the nodes that are currently present in the sorted linked list)\n            else if(newHead->val >= temp->val){\n                temp->next = newHead;\n                newHead = temp;\n            }\n            // inserting the node anywhere in the middle or in the end depending upon the value of the temp node;\n            else{\n                ListNode* root = newHead;\n                {\n                while(root->next){\n                    if(temp->val > root->val and temp->val <= root->next->val){\n                        temp->next = root->next;\n                        root->next = temp;\n                        break;\n                    }\n                    root = root->next;\n                }  \n                    //inserting the temp node at the end\n                    if(root->next==NULL) root->next = temp;\n                    \n                }\n            }\n        }\n        //Our sorted linkedlist\n        return newHead;\n    }\n};\n```\n
['Linked List', 'C', 'C++']