Beats 87.86 % of java submissions


  • 0
    L
        public ListNode insertionSortList(ListNode head) {
            if(head == null || head.next == null) {
                return head;
            }
            //Dummy head
            ListNode dummyHead = new ListNode(-1);
            dummyHead.next = head;
    
            ListNode pre=null, curr=head, insert=null;
            while(curr!=null) {
                //Scroll curr node until decrease.
                while(curr.next!=null && curr.val< curr.next.val) {
                    curr = curr.next;
                }
    
                if(curr.next== null) {
                    break;
                }
    
                //Find insert slot
                insert = curr.next;
                pre = dummyHead;
                while(pre.next.val<insert.val) {
                    pre = pre.next;
                }
    
                //Insert
                curr.next = insert.next;
                insert.next = pre.next;
                pre.next = insert;
    
            }
    
            //Return the head of link
            return dummyHead.next;
        }
    

Log in to reply
 

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