Java solution, Beats 96%, very easy to understand and well commented


  • 0
    V
     public ListNode insertionSortList(ListNode head) {
           ListNode sortedHead  = null, sortedTail = null;
            while(head != null){
                ListNode next = head.next;
                if(sortedHead == null){ // for first item.
                    sortedHead = sortedTail = head;
                    sortedHead.next = sortedTail.next = null;
                }else if (head.val >= sortedTail.val){ // already in best position i.e larger than tail
                    sortedTail.next = head;
                    sortedTail = sortedTail.next;
                }else if (sortedHead.val >= head.val){ // will be inserted in first position, smaller than first item in current list.
                	head.next = sortedHead;
                	sortedHead = head;
                }else{ // find the postion in already sorted list and add the node at that point
                	ListNode start = sortedHead;
                	ListNode prev = start; // importnat for inserting node.
                	while(start != null && start.val < head.val){
                		prev = start;
                		start = start.next;
                	}
                	// appending operation.
                	head.next = start;
                	prev.next = head;
                }
                sortedTail.next = null; // to prevent for cycle.
                head = next;
            }
            
            return sortedHead;
        }

Log in to reply
 

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