Just switch values instead of pointers when switch nodes


  • 0
    L

    My accepted C++ approach is explained in the comments.

      class Solution {
        public:
            ListNode *insertionSortList(ListNode *head) {
                if (head == NULL || head->next == NULL)
                    return head;
                    
                ListNode *p = head;
                int n = 0;
                
                while (p != NULL)       // calculate the number of nodes
                {
                    n++;
                    p = p->next;
                }
                
                for (int i = n-1; i > 0; i--)
                {
                    p = head;
                    
                    for (int j = 0; j < i-1; j++)       // move pointer to the node that has not sorted
                        p = p->next;
                        
                    while (p->next != NULL)             // insert the node into its following linkedlist
                    {
                        if (p->val > p->next->val)      // just switch the value when do the node switch
                        { 
                            int tt = p->val;
                            p->val = p->next->val;
                            p->next->val = tt;
                        
                            p = p->next;
                        }  
                        else
                            break;
                    }
                }
                
                return head;
            }
        };

Log in to reply
 

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