A elegant Method using ListNode**, O(1) Space,C++


  • 1
    class Solution {
    public:
        ListNode* insertionSortList(ListNode* head) {
            ListNode** now=&head;
            while((*now)!=nullptr){
                ListNode* tmp=(*now);//tmp is the node for insert
                ListNode** ins=&head;
                while((*ins)->val<tmp->val && ins!=now){//find the place to insert, actually we can use bsearch to shorten the time
                    ins=&((*ins)->next);
                }
                if(ins !=now){ //if tmp need to insert,update now and insert
                	(*now)=(*now)->next;
    				tmp->next=(*ins);
                	(*ins)=tmp;
    			}else {//if not,just update now
    				now=&((*ins)->next);
    			}
            }
            return head;
        }
    };
    

    The basic idea is to get and change the value of Node.next instead of the node.


Log in to reply
 

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