Easy to Understand Java Code with Detailed Explanation


  • 0
    M
    public class Solution {
    public ListNode insertionSortList(ListNode head) {
    
        if(head==null||head.next==null) return head;
        
        //1. There's no requirement of in-place or constant space, so we create a new list(result list) to store result, its head is dummy.
        
        ListNode dummy = new ListNode(0);
        
        //2. Traverse all nodes in unsorted list, for each node(node n) inside unsorted list, traverse through the result list to find the first node whose value is larger than current node(node n).
        
        while(head!=null){
            ListNode resultTraverse = dummy;
            while(resultTraverse.next!=null&&resultTraverse.next.val < head.val){
                resultTraverse = resultTraverse.next;
            }
            
            //3. Once we've found the larger node in result list, we can insert current node(node n) before the found larger node in result list.
            ListNode temp = head.next;
            head.next = resultTraverse.next;
            resultTraverse.next = head;
            head = temp;
        }
        return dummy.next;
        
        // How to insert a node(from another list) before a particular node in result list?
        // Unsorted list: 1->2->3, result list: D->5, assume we want to insert nodeWithValue1 before nodeWithValue5, we know the dummy node(node D) of result list.
        // 1. Store list next to nodeWithValue1: ListNode temp = nodeWithValue1.next
        // 2. Link nodeWithValue1 to nodeWithValue5: nodeWithValue1.next = D.next.
        // (After step 2 the list will be: 1->5)
        // 3. Link dummy node to nodeWithValue1: D.next = nodeWithValue1
        // (After step 3 the list will be: D->1->5)
        // Go the next node in unsorted list: head = temp
        // (Now the pointer in unsorted list will point to nodeWithValue2)
    }
    

    }


  • 0
    Y

    just a question, since one big advantage of insertion sort is that it is fast when the given array of numbers are partially sorted. But if we insert from beginning of the result array, it would not be any faster when the array is partially sorted right?


Log in to reply
 

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