[recommend for beginners]clean C++ implementation with detailed explaination


  • 6

    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;
        }
    };

  • 0
    M
    This post is deleted!

  • 0
    /**
     * 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;
        }
    };

  • 0
    /**
     * 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;
        }
    };

  • 0
    2

    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;
        }
    };

Log in to reply
 

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