Learning Journal

1/26/2024

Insertion Sort List #2 attempt

Tags: algorithms leetcode insertion_sort

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */


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

    while(pos !== null) {
        const curNode = pos;
        let newPrevPos = dummy;


        while(newPrevPos.next !== null && newPrevPos.next.val <= curNode.val) {
            newPrevPos = newPrevPos.next;
        }
        
        pos = pos.next;
        
        curNode.next = newPrevPos.next;
        newPrevPos.next = curNode;
    }

    return dummy.next;
};


/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */


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

    while(pos !== null) {
        const curNode = pos;
        let newPrevPos = dummy;


        while(newPrevPos.next !== null && newPrevPos.next.val <= curNode.val) {
            newPrevPos = newPrevPos.next;
        }
        
        pos = pos.next;
        
        curNode.next = newPrevPos.next;
        newPrevPos.next = curNode;
    }

    return dummy.next;
};

This is my second attempt solving the problem Insertion Sort List

Here is something that I learned during this attempt:

Actually, there are two lists: the old list that is given to us and the new list that we create by putting elements from the old list, one by one, in the sorted order and then returning it.
I used the pointer pos to keep track of the current position in the old list and dummy node to get a hold of the new list.
After each iteration, one node will be cut off from the old list and moved to the new list. The pos pointer always points to the beginning of the already cut off old list. Thus, we need to move it to the next node BEFORE we cut off the current element from the old list.