[recommend for beginners]clean C++ implementation with detailed explaination
This problem is all about details, you just need to check what to do when insert the cur-pointer to the linked-list.\n\nYou need to consider 2 cases carefully. 
This problem is all about details, you just need to check what to do when insert the cur-pointer to the linked-list.\n\nYou need to consider 2 cases carefully. I believe it is all about details.\n\n    class  Solution {\n    public:\n        ListNode* insertionSortList(ListNode* head) {\n            if(!head)   return NULL;\n            ListNode* dummy=new ListNode(-1);\n            dummy->next=head;\n            ListNode *cur=head->next, *prev=head;\n            while(cur){\n                //record the next pointer \n                ListNode* nextPtr=cur->next;\n                //find the inserted position from the dummy start position\n                ListNode *prePtr=dummy;\n                ListNode *curPtr=dummy->next;\n                while(curPtr!=cur && curPtr->val <= cur->val){\n                    prePtr=prePtr->next;\n                    curPtr=curPtr->next;\n                }\n                /* check the current position  */\n                /* case 1 : we need to insert it  */\n                if( curPtr!= cur ){\n                     prePtr->next = cur;\n                     cur->next = curPtr;\n                     prev->next = nextPtr;\n                     cur=nextPtr;\n                }\n                /* case 2 : we do not need to insert it */\n                else{\n                    prev=cur;\n                    cur=cur->next;\n                }\n            }\n            return dummy->next;\n        }\n    };
[]