Java Solution In-Place Insertion Sort.


  • 1
    public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        ListNode node,pre=dummy,cur=head.next,next=null;
        head.next=null;
        while(cur!=null){
            pre=dummy;   //start from the dummy each time
            for(node=dummy.next;node!=null;node=node.next){
                if(node.val>cur.val||node.val==cur.val){
                    next=cur.next;
                    pre.next=cur;
                    cur.next=node;
                    break;
                }
                pre=node;
            }
            if(node==null){               //the cur node is larger than all the nodes in the pre-sorted List starting from dummy node. so add it to its tail.
                pre.next=cur;
                next=cur.next;
                cur.next=null;     //don't forget to point to NULL.
            }
             cur=next; 
         }
        return dummy.next;
    }
    

    }


Log in to reply
 

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