# [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.

You need to consider 2 cases carefully. I believe it is all about details.

``````class  Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if(!head)   return NULL;
ListNode* dummy=new ListNode(-1);
dummy->next=head;
ListNode *cur=head->next, *prev=head;
while(cur){
//record the next pointer
ListNode* nextPtr=cur->next;
//find the inserted position from the dummy start position
ListNode *prePtr=dummy;
ListNode *curPtr=dummy->next;
while(curPtr!=cur && curPtr->val <= cur->val){
prePtr=prePtr->next;
curPtr=curPtr->next;
}
/* check the current position  */
/* case 1 : we need to insert it  */
if( curPtr!= cur ){
prePtr->next = cur;
cur->next = curPtr;
prev->next = nextPtr;
cur=nextPtr;
}
/* case 2 : we do not need to insert it */
else{
prev=cur;
cur=cur->next;
}
}
return dummy->next;
}
};``````

• This post is deleted!

• ``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(INT_MIN);
ListNode *cur, *next;

while(head){
cur=&dummy;
while(cur->next && cur->next->val < head->val){
cur=cur->next;
}
/** record the next node **/
next=head->next;
/** insert the head to the find pos **/
head->next=cur->next;
cur->next=head;
/** move the head to next **/
head=next;
}

return dummy.next;
}
};``````

• ``````/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(INT_MIN);
ListNode *cur, *next;

while(head){
cur=&dummy;
while(cur->next && cur->next->val < head->val){
cur=cur->next;
}
/** record the next node **/
next=head->next;
/** insert the head to the find pos **/
head->next=cur->next;
cur->next=head;
/** move the head to next **/
head=next;
}

return dummy.next;
}
};``````

• I have to admit the below answering post solution is really beautiful !!!!!!!!!

``````class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
ListNode dummy(-1);
ListNode *cur, *next;
while(head) {
cur = &dummy;
next = head->next;
while(cur->next && cur->next->val < head->val) {
cur = cur->next;
}
head->next = cur->next;
cur->next = head;
head = next;
}
return dummy.next;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.