A simple and intutive solution using fake pointer as starting node


  • 0
    N
    
    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode *result = new ListNode(INT_MIN);
            while(head){
                ListNode *iter = (result);
                while(iter->next and iter->next->val<head->val){
                    iter = iter->next;
                }
                ListNode *nxt = head->next;
                ListNode *temp = iter->next;
                iter->next = head;
                head->next = temp;
                head = nxt;
            }
            return result->next;
        }
    };
    
    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode *temp = head;
            while(temp){
                ListNode *newhead = head;
                while(newhead!=temp and newhead->val<temp->val){
                    newhead = newhead->next;
                }
                if(newhead==temp){
                    temp = temp->next;
                    continue;
                }
                int p;
                if(newhead){
                    p = newhead->val;
                    newhead->val = temp->val;
                    newhead = newhead->next;
                }
                while(newhead and newhead!=temp){
                    int pr = newhead->val;
                    newhead->val = p;
                    newhead = newhead->next;
                    p = pr;
                }
                temp->val = p;
                temp = temp->next;
            }
            return head;
        }
    };
    
    

Log in to reply
 

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