9ms Java, beats 90%


  • 0
    F

    The code may be tedious, but it's effective in solving this problem.

    public class Solution {
        public ListNode insertionSortList(ListNode head) {
            if(head!=null && head.next!=null){
                ListNode curHead = head;
                ListNode curTail = head;
                ListNode curNode = head.next;
                ListNode nxtNode = head.next.next;
                ListNode curInsertNode;
                ListNode preInsertNode;
                
                head.next = null;
                while(curNode != null){
                    if(curNode.val >= curTail.val){
                        //If the current value is larger than the tail of the current sorted list, then insert the current node at the tail
                        curNode.next = curTail;
                        curTail = curNode;
                    } else if(curHead.val > curNode.val) {
                        //If the current value is smaller than the head of the current sorted list, then insert the current node at the head
                        curHead.next = curNode;
                        curHead = curNode;
                        curNode.next = null;
                    } else {
                        //If the current value is somewhere in between
                        curInsertNode = curTail;
                        preInsertNode = null;
                        while(curInsertNode.val > curNode.val){
                            //Start from the tail, go all the way back to the head to check where to insert the current node.
                            preInsertNode = curInsertNode;
                            curInsertNode = curInsertNode.next;
                        }
                        //Insert the node at the proper position
                        preInsertNode.next = curNode;
                        curNode.next = curInsertNode;
                    }
                    
                    //Move to the next node
                    curNode = nxtNode;
                    if(nxtNode != null){
                        nxtNode = nxtNode.next;
                    }
                }
                
                //The list obtained in the while iteration is reversed. So, we need to reverse the list again.
                head = reverse(curTail);
            }
            
            return head;
        }
        
        private ListNode reverse(ListNode list) 
        {
            if(list==null || list.next==null)
            {
                return list;
            }
            
            ListNode back = list;
            ListNode mid = list.next;
            ListNode front = list.next.next;
            list.next = null;
            while(front != null)
            {
                mid.next = back;
                back = mid;
                mid = front;
                front = front.next;
            }
            mid.next = back;
            
            return mid;
        }
    }

Log in to reply
 

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