Learning Journal

1/26/2024

Insertion Sort List

Tags: algorithms leetcode insertion_sort

function insertionSortList(head: ListNode | null): ListNode | null {
    let curr = head;
    const dummy = new ListNode();

    while(curr !== null) {
        let prev = dummy;
    
        while(prev.next !== null && prev.next.val <= curr.val){
            prev = prev.next;
        }

        const next = curr.next;
        curr.next = prev.next;
        prev.next = curr;
        curr = next;
    }

    return dummy.next;
};function insertionSortList(head: ListNode | null): ListNode | null {
    let curr = head;
    const dummy = new ListNode();

    while(curr !== null) {
        let prev = dummy;
    
        while(prev.next !== null && prev.next.val <= curr.val){
            prev = prev.next;
        }

        const next = curr.next;
        curr.next = prev.next;
        prev.next = curr;
        curr = next;
    }

    return dummy.next;
};

This is the solution for the Insertion Sort List problem. First, we create a dummy node and a pointer curr that points to head.

Then, in the outer while loop, we make the pointer curr advance one element by one element until it reaches the end of the array (curr === null). Two statements that makes the pointer advance is const next= curr.next; curr = next;

Then, we create another pointer named prev that points to dummy. In the first iteration, dummy.next is pointed to null, thus, the inner while loop is not executed. Then, we make the head.next point to null and make the dummy pointer points to head. Now, the dummy pointer points to head and curr point to the one after that.

Next iteration, we start at dummy node again, now it points to head. and curr point the the one after that. Now, in the inner loop, we move prev until it reach the place where curr should be (prev.next.val > curr.val). Then, we move curr to prev's place and prev will become the one right before it.