Accepted Java Solution


  • 0
    W
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) {
     *         val = x;
     *         next = null;
     *     }
     * }
     */
    public class Solution {
        public ListNode insertionSortList(ListNode head) {
            
            if(head == null)return null;
            if(head.next == null)return head;
            
            ListNode now = head.next, h = head, t=head, p=head, q=head;
            
            while(now!=null){
                
                if(now.val <= h.val){
                    // current value is less than head value, so update head
                    t.next = now.next;
                    now.next = h;
                    h = now;
                }else{
                    
                    p=h;
                    q=p;
                    
                    // find the position to insert current value
                    while(p.val<now.val){
                        if(p==now)break;
                        q=p;
                        p=p.next;
                    }
                    
                    // p==now because current value is the greatest value evaluated so far
                    // just set current value as new tail
                    if(p==now)t=t.next;
                    else{
                        
                        t.next = now.next;
                        now.next = p;
                        q.next = now;
                    }
                }
                
                // continue to evaluate next value 
                now = t.next;
            }
            
            return h;
        }
    }

Log in to reply
 

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