7ms Java O(1) simple solution


  • 0
    A
        public ListNode insertionSortList(ListNode head) {
            if (head == null || head.next == null)
                return head;
            
            ListNode prev = head;
            ListNode curr = prev.next;
            ListNode after;
    
            while (curr != null) {
                after = curr.next;
                if (curr.val >= prev.val)
                    prev = curr;
                else {
                    ListNode tprev = null;
                    ListNode temp = head;
                    while (temp != curr) {
                        if (curr.val <= temp.val) {
                            if (tprev == null)
                                head = curr;
                            else
                                tprev.next = curr;
                            curr.next = temp;
                            prev.next = after;
                            break;
                        } else {
                            tprev = temp;
                            temp = temp.next;
                        }
                    }
                }
                curr = after;
            }
            return head;
        }
    

Log in to reply
 

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